Byteland 政府决定将他们的小国接入互联网，以便所有公民都能参加编程竞赛并观看可爱的猫咪视频。在构建国家网络骨干网时，他们委托 Internet Optimists Inc. 公司连接 Byteland 的所有 $n$ 台计算机。连接方式是在计算机对之间建立直接链路，使得任意两台计算机之间都有一条链路序列相连。

Byteland 并不是一个富裕的国家，因此为了最小化成本，网络拓扑结构被建成了一棵树（即恰好有 $n-1$ 条计算机之间的直接链路）。后来人们才意识到，这个方案存在一个严重的缺陷。如果仅仅是一条链路断开，Byteland 的计算机就会被分割，导致某些计算机之间无法通信！

为了提高 Byteland 网络的可信度，决定将其改造为至少能容忍一条链路断开的情况。你的任务是帮助 Internet Optimists Inc. 以最廉价的方式改进网络。给定 Byteland 的网络拓扑（即哪 $n-1$ 对计算机之间有直接链路），求出需要添加的最少链路数，使得即使任意一条链路断开，网络仍然保持连通。

输入格式

输入的第一行包含一个正整数 $n$ ($n \ge 3$)，表示 Byteland 的计算机数量。为简便起见，所有计算机编号从 $1$ 到 $n$。接下来的 $n-1$ 行，每行包含一对整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，描述了计算机 $a$ 和 $b$ 之间的一条直接链路。

输出格式

输出的第一行应包含一个整数 $k$，表示需要添加到网络中的最少链路数。在接下来的 $k$ 行中，每行应输出一对整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，表示应该通过链路连接的计算机编号。链路可以按任意顺序输出。如果存在多种方案，输出其中任意一种即可。

样例

样例输入 1

6
1 2
2 3
2 4
5 4
6 4

样例输出 1

2
1 5
3 6

样例输入 2

8
1 2
2 3
3 4
4 5
3 6
3 7
3 8

样例输出 2

3
1 6
5 7
8 4

子任务