Fişierul intrare/ieşire:nustiu.in, nustiu.outSursăONIS 2014, Runda Finala
AutorDr ViorelAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.2 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nu stiu

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.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 10.000
  • 1 ≤ x, y ≤ N

Exemplu

nustiu.innustiu.out
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

Explicaţii

Pentru primul test, se pot inunda intersecţiile 3 şi 4, iar pentru al doilea, intersecţiile 1 şi 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content