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") ==