与えられた木に対して、結果として得られるグラフがサボテングラフ（cactus graph）となるように、できるだけ多くの辺を追加せよ。

サボテングラフとは、すべての辺が高々一つの単純サイクルに含まれるグラフのことである。このグラフは、自己ループや多重辺を含んではならない。

入力

1行目に、木のサイズを表す整数 $N$ ($1 \le N \le 200\,000$) が与えられる。 続く $N - 1$ 行の各行には、2つの整数 $u$ と $v$ ($1 \le u, v \le N, u \neq v$) が与えられ、ノード $u$ と $v$ の間に辺があることを示す。与えられるグラフは木であることが保証されている。

出力

1行目に、グラフに追加できる辺の最大数 $K$ を出力せよ。続く $K$ 行の各行に、ノード $a$ と $b$ ($1 \le a, b \le N, a \neq b$) を出力せよ。これはノード $a$ と $b$ の間に辺を追加することを意味する。結果として得られるグラフはサボテングラフでなければならない。

最大数 $K$ を達成する解が複数存在する場合は、そのうちのどれを出力してもよい。

入出力例

入力 1

6
6 4
3 1
3 6
4 5
2 3

出力 1

2
2 1
3 5