UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3546. [ONTAK2010]Life of the Party

Statistics 下载数据

Description

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

Input

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

Output

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

Sample Input

4 4 4
2 1
3 2
4 3
4 4

Sample Output

2
3
4
1
2


Hint

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

Source

By Sbullet