Piggy (der in seiner Freizeit die Kommission für Interstellare Konnektivitätsprotokolle leitet) steht vor einem heiklen Hardware-Rätsel. Das neueste Kommunikationsnetz, bestehend aus $n$ Relaisstationen, die durch $(n - 1)$ Glasfaserverbindungen zu einer Baumstruktur verbunden sind, ist endlich einsatzbereit. Allerdings muss das System mit äußerster Vorsicht eingeschaltet werden.
Der Aktivierungsprozess beinhaltet das Abfeuern von Laserimpulsen entlang bestimmter Pfade. Ein Pfad ist definiert als die eindeutige einfache Verbindung zwischen zwei Stationen. Wegen des katastrophalen Risikos einer „Quanten-Rückfluss-Interferenz“ — eines Phänomens, das den Anwälten der Kommission schlaflose Nächte bereitet — muss das folgende Protokoll strikt eingehalten werden:
- Übertragungspfade müssen nacheinander einzeln eingerichtet werden.
- Um Spannungsspitzen zu vermeiden, darf jeder neu eingerichtete Pfad höchstens eine Station mit der Menge der Stationen gemeinsam haben, die bereits durch einen vorherigen Pfad aktiviert wurden.
Formal sei $S$ die Menge der aktuell aktivierten Stationen. Für jeden neuen Pfad $P$, der aus einer Menge von Stationen $V(P)$ besteht, muss die Bedingung $|V(P) \cap S| \le 1$ gelten. Sobald ein Pfad erfolgreich abgefeuert wurde, gelten alle Stationen entlang dieses Pfades als Teil der aktivierten Menge $S$.
Ihre Mission, sollten Sie diese annehmen, besteht darin, die minimale Anzahl von Laserimpulsen zu bestimmen, die erforderlich ist, um jede Station im gesamten Netzwerk zu aktivieren, und eine solche Folge von Pfaden anzugeben, um die Rechtsabteilung zufriedenzustellen.

Die Darstellung der ersten beiden Beispieltestfälle. Beachten Sie, dass in Fall 2 der zweite Impuls nur Station $2$ mit dem ersten teilt und somit die Nicht-Interferenz-Regel erfüllt.
Eingabe
Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:
Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 3 \times 10^5$), die Anzahl der Stationen im Netz.
In den folgenden $(n - 1)$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), die eine bidirektionale Glasfaserverbindung zwischen Station $u_i$ und Station $v_i$ beschreiben.
Es wird garantiert, dass die Verbindungen einen Baum bilden und dass die Summe von $n$ über alle Testfälle $3 \times 10^5$ nicht überschreitet.
Ausgabe
Geben Sie für jeden Testfall in der ersten Zeile die minimale Anzahl von Pfaden $k$ aus. Geben Sie anschließend $k$ Zeilen aus, die jeweils zwei ganze Zahlen $a_i$ und $b_i$ enthalten, welche die Endpunkte des $i$-ten Pfades in der Folge darstellen. Beachten Sie, dass $a_i$ gleich $b_i$ sein kann, wenn der Pfad aus einer einzigen Station besteht.
Falls mehrere optimale Folgen existieren, wird jede akzeptiert, die das Nicht-Interferenz-Protokoll strikt einhält.
Beispiel
Eingabe
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
Ausgabe
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5