Piggy (który w wolnym czasie zarządza Komisją ds. Protokołu Łączności Międzygwiezdnej) stoi przed delikatnym problemem sprzętowym. Najnowsza sieć komunikacyjna, składająca się z $n$ stacji przekaźnikowych połączonych $(n-1)$ łączami światłowodowymi tworzącymi strukturę drzewa, jest wreszcie gotowa do wdrożenia. System musi jednak zostać uruchomiony z zachowaniem szczególnej ostrożności.

Proces aktywacji polega na wysyłaniu impulsów laserowych wzdłuż określonych ścieżek. Ścieżka jest zdefiniowana jako unikalna prosta droga między dwiema stacjami. Ze względu na katastrofalne ryzyko „zakłóceń kwantowego przepływu zwrotnego” — zjawiska, które spędza sen z powiek prawnikom komisji — należy ściśle przestrzegać następującego protokołu:

• Ścieżki transmisji muszą być ustanawiane jedna po drugiej.
• Aby zapobiec skokom napięcia, każda nowo ustanowiona ścieżka może współdzielić co najwyżej jedną stację ze zbiorem stacji już aktywowanych przez jakąkolwiek poprzednią ścieżkę.

Formalnie, niech $S$ będzie zbiorem aktualnie aktywowanych stacji. Dla każdej nowej ścieżki $P$ składającej się ze zbioru stacji $V(P)$, musi być spełniony warunek $|V(P) \cap S| \le 1$. Gdy ścieżka zostanie pomyślnie uruchomiona, wszystkie stacje wzdłuż tej ścieżki są uważane za część zbioru aktywowanego $S$.

Twoim zadaniem, jeśli zdecydujesz się je przyjąć, jest wyznaczenie minimalnej liczby impulsów laserowych wymaganych do aktywacji każdej stacji w całej sieci oraz podanie jednej takiej sekwencji ścieżek, która zadowoli dział prawny.

Ilustracja pierwszych dwóch przykładowych przypadków testowych. Zauważ, że w przypadku 2 drugi impuls współdzieli z pierwszym tylko stację 2, spełniając zasadę braku zakłóceń.

Wejście

Dostępnych jest wiele przypadków testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) określającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwsza linia zawiera liczbę całkowitą $n$ ($2 \le n \le 3 \times 10^5$), liczbę stacji w sieci.

Dla kolejnych $(n-1)$ linii, $i$-ta linia zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), opisujące dwukierunkowe łącze światłowodowe między stacją $u_i$ a stacją $v_i$.

Gwarantuje się, że łącza tworzą drzewo oraz że suma $n$ we wszystkich przypadkach testowych nie przekracza $3 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w pierwszej linii minimalną liczbę ścieżek $k$. Następnie wypisz $k$ linii, z których każda zawiera dwie liczby całkowite $a_i$ oraz $b_i$, reprezentujące punkty końcowe $i$-tej ścieżki w sekwencji. Zauważ, że $a_i$ może być równe $b_i$, jeśli ścieżka składa się z pojedynczej stacji.

Jeśli istnieje wiele optymalnych sekwencji, każda, która ściśle przestrzega protokołu braku zakłóceń, zostanie zaakceptowana.

Przykład

Wejście 1

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

Wyjście 1

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