对于一棵有根树 $A$ 和一个大于等于 $2$ 的整数 $B$，定义无根树 $A * B$ 如下：

• 将树 $A$ 复制 $B$ 次，得到 $B$ 棵树 $A_1, A_2, \ldots, A_B$，然后对于所有 $1 \le i < B$，连接 $A_i$ 的根节点与 $A_{i+1}$ 的根节点。

给定一棵无根树 $C$，求出一棵有根树 $A$ 和一个大于等于 $2$ 的整数 $B$，使得 $C = A * B$。

题目保证存在满足 $C = A * B$ 的有根树 $A$ 和整数 $B$。

若存在多种可能的答案，输出其中任意一个即可。

对于两棵无根树 $T_1$ 和 $T_2$，若忽略顶点编号后两者的形状相同，则认为 $T_1 = T_2$。

输入格式

第一行包含一个整数 $N$，表示树 $C$ 的顶点数。 $(2 \le N \le 100\,000)$

接下来的 $N-1$ 行，每行包含两个整数 $u, v$，表示树 $C$ 的一条边的两个端点。$(1 \le u, v \le N)$

输出格式

第一行输出整数 $B$。

第二行输出树 $A$ 的顶点数 $M$。

接下来的 $M-1$ 行，每行输出两个整数 $u, v$，表示树 $A$ 的一条边的两个端点。$(1 \le u, v \le M)$

树 $A$ 的根节点为顶点 $1$。

样例

样例输入 1

4
1 2
2 3
3 4

样例输出 1

4
1

样例输入 2

6
1 2
1 3
1 4
4 5
4 6

样例输出 2

2
3
1 2
1 3