bzoj#P3546. [ONTAK2010] Life of the Party

[ONTAK2010] Life of the Party

题目描述

一个舞会有 nn 个男孩(编号为 1n1 \dots n)和 mm 个女孩(编号为 1m1 \dots m),一对男女能够组成一对跳舞当且仅当他们两个人互相认识。

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

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

输入格式

第一行 33 个整数 nnmmkk,表示 mm 个男生,mm 个女生,kk 对关系。

接下来 kk 行,每行两个整数 aia_ibib_i,表示第 aia_i 个男生和第 bib_i 个女生相互认识。

输出格式

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

4 4 4
2 1
3 2
4 3
4 4
2
3
4
1
2

提示

n,m104, k105n,m \le 10^4,~k \le 10^5

题目来源

By Sbullet