题目描述

给你两棵森林，节点数均为 $n$。

允许你进行加边操作，但是有两个要求：

• 如果在第一个森林加一条 $(u,v)$ 的边，第二个森林也要进行同样的操作。反之同理。
• 加边后两个森林依旧是森林。（一棵树也是森林）

求最多能加几条边，并输出加边方案。

输入格式

第一行三个整数 $n,m_1,m_2$（ $1 \le n \le 1000,0 \le m_1,m_2 < n$ ），分别表示结点数，第一个森林的边数，第二个森林的边数。

接下来 $m_1$ 行，每行两个整数 $u,v$ ( $1 \le u,v \le n, u \ne v$ )，用来描述第一个森林。

接下来 $m_2$ 行，每行两个整数 $u,v$ ( $1 \le u,v \le n, u \ne v$ )，用来描述第二个森林。

输出格式

第一行一个整数表示最多加边数。

接下来每行两个整数 $u,v$ 表示所加的边。

样例

3 2 2
1 2
2 3
1 2
1 3

0

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

1
2 4

8 1 2
1 7
2 6
1 5

5
5 2
2 3
3 4
4 7
6 8