[ONTAK2010]Life of the Party

时间限制:10s      空间限制:32MB

题目描述

一个舞会有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


题目来源

By Sbullet