== include(page="template/taskheader" task_id="linegraph") ==

Poveste şi cerinţă...

Cătălin, după ce s-a jucat destul la bunici, a ajuns acasă, dar nu a venit cu mâna goală, ci a adus cu el cel mai frumos arbore pe care l-a avut în jocul “TreeGCD”, desenat pe o hârtie. Acasă, fratele lui mai mic a găsit această foaie şi s-a gândit să îşi încerce talentul la desen. El vrea să transforme arborele într-un graf în următorul fel: fiecare muchie din arborele iniţial devine un nod în noul graf, două noduri din noul graf sunt legate printr-o muchie dacă şi numai dacă cele două muchii corespunzătoare din arborele iniţial au un nod în comun.
După ce a construit acest graf, el a aruncat hârtia cu arborele iniţial. Când s-a întors de la şcoală, Cătălin, văzând ceea ce s-a întâmplat, nu a fost prea fericit. Din fericire, a aflat că voi puteţi să reconstruiţi arborele iniţial, dacă vă dă graful.
h1. Cerinta

Se dau numărul N de noduri, numărul M de muchii şi cele M muchii din graf. Reconstruiţi arborele iniţial.

Se dau numărul $N$ de noduri, numărul $M$ de muchii şi cele $M$ muchii din graf. Reconstruiţi arborele iniţial.

Este posibil ca fratele lui Cătălin să fi desenat greşit graful şi să nu existe un arbore asociat.
h2. Date de intrare

Fişierul de intrare $linegraph.in$ ...

În fişierul de intrare $linegraph.in$ pe prima linie se află un număr $T$, ce reprezintă numărul de teste din fişier. Pentru fiecare test pe prima linie se află două numere naturale $N$ şi $M$ separate prin spaţiu cu semnificaţiile din enunţ, iar pe următoarele $M$ linii se află câte două numere separate prin spaţiu, ce reprezintă nodurile care au o muchie între ele.

h2. Date de ieşire

În fişierul de ieşire $linegraph.out$ ...

În fişierul de ieşire $linegraph.out$ pe prima linie trebuie să se afişeze fie cuvântul *NU*, dacă nu există un arbore asociat grafului dat, fie cuvântul *DA*, dacă există arbore asociat, şi în acest caz pe următoarea linie se va afişa un număr $E$, ce reprezintă numărul de noduri din arbore, şi pe următoarele $E-1$ linii se vor afişa câte două numere ce reprezintă perechile de noduri din arbore, care au o muchie între ele.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1$ ≤ $T$ ≤ $10.000$
* $1$ ≤ $N$ ≤ $1.000$
* $0$ &le; $M$ &le; <tex> \frac{N*(N-1)}{2} </tex>
* suma pătratelor tuturor $N$-urilor din fişierul de intrare nu depăşeşte $1.000.000$;
* pentru teste în valoare de $15$ puncte, se garantează că există soluţie şi că arborele din care s-a construit graful are fie formă de lanţ, fie are $N-1$ frunze;
* pentru alte teste în valoare de $55$ de puncte, se garantează că $N$ ≤ $100$ şi suma pătratelor tuturor N-urilor din fişierul de intrare nu depăşeşte $10.000$;
* dacă există mai multe soluţii, se poate afişa oricare dintre ele;
* arborele din fişierul de ieşire cu $E$ noduri va avea nodurile numerotate cu $1,2,...,E$;
* numerotarea efectivă a nodurilor din fişierul de ieşire nu este importantă – orice soluţie ce renumerotează nodurile va fi considerata un răspuns corect.
 

h2. Exemplu
table(example). |_. linegraph.in |_. linegraph.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
5 7
3 2
3 5
3 1
2 5
2 1
1 5
1 4
3 1
1 2
| DA
6
1 2
1 3
3 4
3 5
3 6
NU

|
h3. Explicaţie

...

În fişierul de intrare avem un graf. Fiecărei muchii dinacest graf îi corespunde un nod din arborele din fişierul de ieşire. Astfel: muchia $(1,3)$ devine nodul $1$, muchia $(1,2)$ devine nodul $4$, muchia $(3,4)$ devine nodul $3$, muchia $(3,5)$ devine nodul $2$ şi muchia $(3,6)$ devine nodul $5$.
Muchiile $(1,3)$, $(3,4)$, $(3,5)$, $(3,6)$ au toate nodul comun $3$, deci nodurile lor corespunzătoare din graf $(1,3,2,5)$ au toate muchii între ele.
În al doilea test nodul $3$ este izolat şi graful nu poate proveni din niciun arbore.

== include(page="template/taskfooter" task_id="linegraph") ==