| Fişierul intrare/ieşire: | nustiu.in, nustiu.out | Sursă | ONIS 2014, Runda Finala |
| Autor | Dr Viorel | Adăugată de |  Andrei Parvu •andrei.12 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | nustiu.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.
