根付き木 $A$ と $2$ 以上の整数 $B$ に対して、根なし木 $A * B$ を次のように定義する。

• 木 $A$ を $B$ 回複製して $B$ 個の木 $A_1, A_2, \ldots, A_B$ を作り、$1$ 以上 $B$ 未満のすべての $i$ について、$A_i$ の根と $A_{i+1}$ の根を辺で結ぶ。

根なし木 $C$ が与えられるとき、$C = A * B$ となる根付き木 $A$ と $2$ 以上の整数 $B$ を求めよ。

$C = A * B$ となる根付き木 $A$ と $2$ 以上の整数 $B$ が存在する場合のみが与えられる。

可能な答えが複数存在する場合は、そのうちのどれを出力してもよい。

根なし木 $T_1, T_2$ について、頂点番号を無視して $T_1$ と $T_2$ の形状が同じであれば $T_1 = T_2$ とする。

最初の行に木 $C$ の頂点数 $N$ が与えられる。 $(2 \le N \le 100\,000)$

続く $N-1$ 行に、木 $C$ の各辺の端点 $u, v$ が空白区切りで与えられる。 $(1 \le u, v \le N)$

最初の行に整数 $B$ を出力する。

2行目に木 $A$ の頂点数 $M$ を出力する。

3行目から $M-1$ 行にわたって、木 $A$ の各辺の端点 $u, v$ を空白区切りで出力する。 $(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