#3546. [ONTAK2010]Life of the Party

内存限制:32 MiB 时间限制:10 Sec

题目描述

一个舞会有N个男孩(编号为1..N)和M个女孩(编号为1..M),一对男女能够组成一对跳舞当且仅当他们两个人互相认识。
我们把一种人定义成这个舞会的life:当且仅当如果他(她)不参加这个舞会,那么能够同时配对的最大舞伴对数会下降。
现在知道男生和女生之间的认识关系,需要你求出男生和女生中的是这个舞会的life的人的编号。

输入格式

第一行3个整数N,M,K,表示N个男生,M个女生,K对关系。
接下来K行,每行两个整数a_i b_i,表示第a_i个男生和第b_i个女生相互认识。

输出格式

首先输出所有男生中是这个舞会的life的男生的编号,一行一个,从小到大输出,然后输出女生的。

样例

样例输入


			
4 4 4
2 1
3 2
4 3
4 4

样例输出


			
2
3
4
1
2


数据范围与提示

N,M<=10^4,K<=10^5