Cerință
un Omegazoid vrea sa faca un desen cu creionul. Este in clasa a 3-a si acolo e la moda sa faci desene fara sa ridici pixul de pe foaie.
Poate Omegazoidul sa faca desenul fara sa ridice pixul de pe foaie si sa uneasca aceleasi 2 puncte de 2 ori, ba mai mult, desenul sa inceapa din primul punct si sa se termine unde a inceput?
Date de intrare
Pe prima linie se afla (numarul de puncte pe care le are desenul) si (liniile care vrea sa le deseneze intre puncte).
Pe urmatoarele linii sunt cate o pereche de numere , vrea ca punctele si sa fie unite pe desen.
Date de ieșire
sau , depinde daca e posibil (vezi exemplu)
Restricții și precizări
- , .
- Nu se repeta perechile de puncte.
- Daca el are mai multe desene pe aceasi foaie, el trebuie sa completeze doar desenul care conține punctul 1.
Exemplul 1
stdin
3 3
1 2
2 3
1 3
stdout
DA
Explicație
Putem incepe din primul punct de unde sa mergem in al 3-lea, de unde putem merge in al doilea punct, iar apoi inapoi in punctul 1.
Exemplul 2
stdin
5 8
1 5
2 3
5 4
1 4
2 1
4 3
1 3
2 4
stdout
NU
Explicație
Desen:
Nu avem cum.