/ 肥皂剧

题目描述

两位电视剧编剧 Juan 和 Rosa 希望在大结局里安排尽可能多的婚姻。

共有 $n$ 名演员。Juan 和 Rosa 各自给出一些他们认为合适的男女演员配对。

他们希望选出一个尽可能大的演员子集，使得：

• 仅使用 Juan 认可的配对，可以把这个子集里的所有演员两两结婚；
• 仅使用 Rosa 认可的配对，也可以把同一个子集里的所有演员两两结婚。

也就是说，对选出的演员集合，两人的认可图中都必须存在覆盖该集合的完美匹配。

求最多能够安排多少对婚姻，并输出 Juan 和 Rosa 各自的一组对应配对方案。

题目保证所有给出的关系都只连接一男一女，因此所有关系的并图是二分图。

输入格式

第一行包含三个整数 $n,m_1,m_2$：

• $n$：演员数；
• $m_1$：Juan 认可的配对数；
• $m_2$：Rosa 认可的配对数。

其中 $2\le n\le100$。

接下来 $m_1$ 行，每行两个整数，表示 Juan 认可的一对演员。

再接下来 $m_2$ 行，每行两个整数，表示 Rosa 认可的一对演员。

同一个人的配对列表中不会出现重复边。

输出格式

第一行输出一个整数 $k$，表示最多可以安排的婚姻数。

接下来输出 $k$ 行，给出 Juan 的一组婚配方案。

随后再输出 $k$ 行，给出 Rosa 的一组婚配方案。

只要满足最优性与所有限制，任意合法方案均可。

样例

4 2 2
1 3
2 4
1 4
2 3

2
1 3
2 4
3 2
4 1

判题说明

本题答案不唯一，需要特殊判题（SPJ）。

时间与空间限制

• 时间限制：0.25 s
• 内存限制：256 MB