这是问题的简单版本。两个版本之间的唯一区别是对 $$$n$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
森林是没有环路(不一定相连)的无向图。
Mocha 和 Diana 是枝江的朋友,他们都有一个森林,节点编号从 $$$1$$$ 到 $$$n$$$,他们想向他们的森林添加边,这样:
- 添加边后,它们的两个图仍然是森林。
- 他们添加相同的边缘。也就是说,如果将边 $$$(u, v)$$$ 添加到 Mocha 的森林,则将边 $$$(u, v)$$$ 添加到 Diana 的森林,反之亦然。
Mocha 和 Diana 想知道他们可以添加的最大边数,以及要添加哪些边。
输入
第一行包含三个整数 $$$n$$$、$$$m_1$$$ 和 $$$m_2$$$ ($$$1 \le n \le 1000$$$, $$$0 \le m_1, m_2 < n$$$) — Mocha 森林和 Diana 森林中的节点数和初始边数。
接下来的 $$$m_1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — Mocha 森林中的边缘。
接下来的 $$$m_2$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — 戴安娜森林中的边缘。
输出
第一行仅包含一个整数 $$$h$$$,Mocha 和 Diana 可以添加的最大边数(在每个森林中)。
接下来的 $$$h$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — 您每次添加的边。
如果有多个正确答案,您可以打印其中任意一个。
示例
输入 #1
3 2 2 1 2 2 3 1 2 1 3
输出 #1
0
输入 #2
5 3 2 5 4 2 1 4 3 4 3 1 4
输出 #2
1 2 4
输入 #3
8 1 2 1 7 2 6 1 5
输出 #3
5 5 2 2 3 3 4 4 7 6 8
注意
在第一个示例中,我们无法添加任何边。
在第二个示例中,初始森林如下。
我们可以添加一条边 $$$(2, 4)$$$。