Mając dane drzewo, dodaj jak najwięcej krawędzi tak, aby wynikowy graf był grafem kaktusowym.

Graf kaktusowy to graf, w którym każda krawędź należy do co najwyżej jednego cyklu prostego. Graf ten nie może zawierać pętli własnych ani krawędzi wielokrotnych.

Wejście

W pierwszej linii znajduje się liczba całkowita $N$, rozmiar drzewa ($1 \le N \le 200\,000$).

Każda z kolejnych $N - 1$ linii zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le N, u \neq v$), wskazujące na istnienie krawędzi między węzłami $u$ oraz $v$. Gwarantuje się, że wynikowy graf jest drzewem.

Wyjście

W pierwszej linii wypisz $K$, maksymalną liczbę krawędzi, które można dodać do grafu. W każdej z kolejnych $K$ linii wypisz dwie liczby całkowite $a$ oraz $b$ ($1 \le a, b \le N, a \neq b$), wskazujące, że dodajesz krawędź między węzłami $a$ oraz $b$. Wynikowy graf musi być grafem kaktusowym.

Jeśli istnieje kilka rozwiązań z maksymalną możliwą liczbą $K$, wypisz dowolne z nich.

Przykład

Wejście 1

6
6 4
3 1
3 6
4 5
2 3

Wyjście 1

2
2 1
3 5