题目描述

一个舞会有 $n$ 个男孩（编号为 $1 \dots n$）和 $m$ 个女孩（编号为 $1 \dots m$），一对男女能够组成一对跳舞当且仅当他们两个人互相认识。

我们把一种人定义成这个舞会的 life：当且仅当如果他（她）不参加这个舞会，那么能够同时配对的最大舞伴对数会下降。

现在知道男生和女生之间的认识关系，需要你求出男生和女生中的是这个舞会的life的人的编号。

输入格式

第一行 $3$ 个整数 $n$，$m$，$k$，表示 $m$ 个男生，$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 \le 10^4,~k \le 10^5$

题目来源

By Sbullet