[ONTAK2010]Life of the Party

题目描述

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