Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 2048 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Piggy (qui, pendant son temps libre, dirige la Commission du Protocole de Connectivité Interstellaire) fait face à un délicat casse-tête matériel. Le tout nouveau réseau de communication, composé de $n$ stations relais reliées par $(n - 1)$ liaisons par fibre optique formant une structure d'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 consiste à tirer des 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 la nuit — le protocole suivant doit être strictement respecté :

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

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 vérifiée. Une fois qu'une impulsion est tirée avec succès sur un chemin, toutes les stations situées le long de ce chemin sont considérées comme faisant partie de l'ensemble activé $S$.

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

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Illustration des deux premiers cas de test de l'exemple. Notez que dans le Cas 2, la deuxième impulsion ne partage que la station $2$ avec la première, respectant 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$-è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 par 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 des $n$ sur l'ensemble des cas de test ne dépasse pas $3 \times 10^5$.

Sortie

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

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

Exemple

Entrée

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 3
2
4 5
1 3
3
7 7
1 6
4 5

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.