Piggy (che, nel tempo libero, dirige la Commissione per il Protocollo di Connettività Interstellare) si trova di fronte a un delicato rompicapo hardware. La nuovissima rete di comunicazione, composta da $n$ stazioni ripetitori collegate da $(n - 1)$ collegamenti in fibra ottica a formare una struttura ad albero, è finalmente pronta per il dispiegamento. Tuttavia, il sistema deve essere acceso con estrema cautela.
Il processo di attivazione prevede l'invio di impulsi laser lungo percorsi specifici. Un percorso è definito come l'unico cammino semplice tra due stazioni. A causa del rischio catastrofico di "Interferenza da Riflusso Quantistico" — un fenomeno che tiene svegli la notte gli avvocati della commissione — è necessario osservare rigorosamente il seguente protocollo:
- I percorsi di trasmissione devono essere stabiliti uno alla volta.
- Per prevenire sovratensioni, ciascun percorso appena stabilito può condividere al massimo una stazione con l'insieme delle stazioni già attivate da qualsiasi percorso precedente.
Formalmente, sia $S$ l'insieme delle stazioni attualmente attivate. Per ogni nuovo percorso $P$ costituito da un insieme di stazioni $V(P)$, deve valere la condizione $|V(P) \cap S| \le 1$. Una volta che un percorso viene attivato con successo, tutte le stazioni lungo quel percorso sono considerate parte dell'insieme attivato $S$.
La tua missione, se deciderai di accettarla, è determinare il numero minimo di impulsi laser necessari per attivare ogni stazione dell'intera rete e fornire una tale sequenza di percorsi per soddisfare l'ufficio legale.

L'illustrazione dei primi due casi di test di esempio. Si noti che nel Caso 2 il secondo impulso condivide solo la stazione $2$ con il primo, soddisfacendo la regola di non interferenza.
Input
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$) che indica il numero di casi di test. Per ciascun caso di test:
La prima riga contiene un intero $n$ ($2 \le n \le 3 \times 10^5$), il numero di stazioni nella rete.
Per le successive $(n - 1)$ righe, la $i$-esima riga contiene due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), che descrivono un collegamento bidirezionale in fibra ottica tra la stazione $u_i$ e la stazione $v_i$.
È garantito che i collegamenti formino un albero e che la somma di $n$ su tutti i casi di test non superi $3 \times 10^5$.
Output
Per ciascun caso di test, stampa il numero minimo di percorsi $k$ sulla prima riga. Di seguito, stampa $k$ righe, ciascuna contenente due interi $a_i$ e $b_i$, che rappresentano gli estremi dell'$i$-esimo percorso nella sequenza. Si noti che $a_i$ può essere uguale a $b_i$ se il percorso è costituito da una singola stazione.
Se esistono più sequenze ottimali, verrà accettata una qualsiasi sequenza che rispetti rigorosamente il protocollo di non interferenza.
Esempio
Input
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
Output
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5