Piggy (który w wolnym czasie zarządza Komisją Protokołu Łączności Międzygwiezdnej) stoi przed delikatnym dylematem sprzętowym. Najnowsza sieć komunikacyjna, składająca się z $n$ stacji przekaźnikowych połączonych za pomocą $(n - 1)$ łączy światłowodowych tworzących strukturę drzewa, jest wreszcie gotowa do wdrożenia. System musi jednak zostać uruchomiony z najwyższą ostrożnością.
Proces aktywacji polega na wystrzeliwaniu impulsów laserowych wzdłuż określonych ścieżek. Ścieżka jest definiowana jako jedyna droga prosta między dwiema stacjami. Ze względu na katastrofalne ryzyko „Kwantowej Interferencji Wstecznej” — zjawiska spędzającego sen z powiek prawnikom komisji — należy ściśle przestrzegać następującego protokołu:
- Ścieżki transmisyjne muszą być ustanawiane jedna po drugiej.
- Aby zapobiec skokom napięcia, każda nowo ustanowiona ścieżka może mieć co najwyżej jedną wspólną stację ze zbiorem stacji aktywowanych już przez jakąkolwiek wcześniejszą ś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 zachodzić warunek $|V(P) \cap S| \le 1$. Gdy ścieżka zostanie pomyślnie aktywowana, wszystkie stacje wzdłuż tej ścieżki stają się częścią aktywowanego zbioru $S$.
Twoją misją, jeśli zdecydujesz się ją przyjąć, jest wyznaczenie minimalnej liczby impulsów laserowych potrzebnych do aktywowania każdej stacji w całej sieci oraz podanie jednego takiego ciągu ścieżek, aby zadowolić dział prawny.

Ilustracja dwóch pierwszych przykładowych przypadków testowych. Zauważ, że w Przypadku 2 drugi impuls dzieli z pierwszym jedynie stację $2$, spełniając zasadę braku interferencji.
Wejście
Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:
Pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 3 \times 10^5$) — liczbę stacji w sieci.
W kolejnych $(n - 1)$ wierszach $i$-ty wiersz 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 wartości $n$ po wszystkich przypadkach testowych nie przekracza $3 \times 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz w pierwszym wierszu minimalną liczbę ścieżek $k$. Następnie wypisz $k$ wierszy, z których każdy zawiera dwie liczby całkowite $a_i$ oraz $b_i$, reprezentujące końce $i$-tej ścieżki w ciągu. 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 ciągów, zaakceptowany zostanie dowolny z nich, który ściśle przestrzega protokołu braku interferencji.
Przykład
Wejście
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 3 2 4 5 1 3 3 7 7 1 6 4 5