== include(page="template/taskheader" task_id="nustiu") ==
Poveste şi cerinţă...
Don Diego tocmai s-a mutat într-un nou oraş care este dispus sub forma unui arbore (graf conex aciclic), cele $N$ intersecţii ale oraşului fiind reprezentate de noduri şi cele $N-1$ drumuri dintre intersecţii prin muchii.
Don Armando, fiind supărat de Don Diego, vrea sa inunde una dintre cele $N$ intersecţii, astfel împărţind oraşul în mai multe componente conexe (intersecţii între care se poate ajunge fără a trece prin intersecţia inundată). Don Armando vrea să producă cât mai multe pagube, şi niciuna dintre componentele conexe rămase să nu conţină mai mult de $N/2$ intersecţii.
Fiindcă nu ştiţi exact ce să faceţi astăzi, vreţi sa aflaţi care sunt intersecţiile pe care Don Armando poate să le inunde astfel încât să respecte proprietatea de mai sus.
h2. Date de intrare
Fişierul de intrare $nustiu.in$ ...
Fişierul de intrare $nustiu.in$ conţine pe prima linie numărul de teste $T$. Urmează $T$ teste.
Prima linie a unui test conţine $N$, numărul de intersecţii din oraş. Următoarele $N-1$ linii conţin două numere $x$ si $y$, reprezentând că există un drum între intersecţiile $x$ si $y$.
h2. Date de ieşire
În fişierul de ieşire $nustiu.out$ ...
În fişierul de ieşire $nustiu.out$ trebuie să afişati, pentru fiecare test, intersecţiile pe care Don Armando le poate inunda astfel încât să respecte cerinţa de mai sus sau mesajul $NIMIC$, dacă nu există nicio astfel de intersecţie. În cadrul unui test, intersecţiile trebuie afişate fiecare pe o linie şi în ordinea crescătoare a indicilor acestora.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 10.000$
* $1 ≤ x, y ≤ N$
h2. Exemplu
table(example). |_. nustiu.in |_. nustiu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
6
1 3
3 2
3 4
4 5
4 6
12
1 2
2 3
2 4
4 5
5 6
5 7
1 8
8 9
8 10
8 11
10 12
| 3
4
1
2
|
h3. Explicaţie
...
h3. Explicaţii
Pentru primul test, se pot inunda intersecţiile $3$ şi $4$, iar pentru al doilea, intersecţiile $1$ şi $2$.
== include(page="template/taskfooter" task_id="nustiu") ==
