Piggy (qui, durant son temps libre, gère la Commission du Protocole de Connectivité Interstellaire) est confronté à un délicat problème matériel. Le dernier réseau de communication, composé de $n$ stations relais reliées par $(n - 1)$ liaisons à fibre optique formant une structure en arbre, est enfin prêt à être déployé. Cependant, le système doit être mis sous tension avec une extrême prudence.

Le processus d'activation implique l'envoi d'impulsions laser le long de chemins spécifiques. Un chemin est défini comme l'unique route simple entre deux stations. En raison du risque catastrophique d'« interférence de reflux quantique » — un phénomène qui empêche les avocats de la commission de dormir — le protocole suivant doit être strictement respecté :

• Les chemins de transmission doivent être établis un par un.
• Pour éviter les surtensions, chaque nouveau chemin établi peut partager au plus une station avec l'ensemble des stations déjà activées par n'importe quel chemin précédent.

Formellement, soit $S$ l'ensemble des stations actuellement activées. Pour tout nouveau chemin $P$ constitué d'un ensemble de stations $V(P)$, la condition $|V(P) \cap S| \le 1$ doit être respectée. Une fois qu'un chemin est activé avec succès, toutes les stations le long de ce chemin sont considérées comme faisant partie de l'ensemble activé $S$.

Votre mission, si vous l'acceptez, est de déterminer le nombre minimum d'impulsions laser nécessaires pour activer chaque station de l'ensemble du réseau et de fournir une telle séquence de chemins pour satisfaire le service juridique.

Illustration des deux premiers cas de test. Notez que dans le cas 2, la deuxième impulsion ne partage que la station 2 avec la première, satisfaisant ainsi la règle de non-interférence.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient un entier $n$ ($2 \le n \le 3 \times 10^5$), le nombre de stations dans le réseau.

Pour les $(n - 1)$ lignes suivantes, la $i$-ième ligne contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), décrivant une liaison bidirectionnelle à fibre optique entre la station $u_i$ et la station $v_i$.

Il est garanti que les liaisons forment un arbre et que la somme de $n$ sur tous les cas de test n'excède pas $3 \times 10^5$.

Sortie

Pour chaque cas de test, affichez le nombre minimum de chemins $k$ sur la première ligne. Ensuite, affichez $k$ lignes, chacune contenant deux entiers $a_i$ et $b_i$, représentant les extrémités du $i$-ième chemin dans la séquence. Notez que $a_i$ peut être égal à $b_i$ si le chemin consiste en une seule station.

Si plusieurs séquences optimales existent, n'importe laquelle respectant strictement le protocole de non-interférence sera acceptée.

Exemples

Entrée 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

Sortie 1

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