Desen

Time limit: 1s Memory limit: 64MB Input: Output:

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 NN (numarul de puncte pe care le are desenul) si MM (liniile care vrea sa le deseneze intre puncte).
Pe urmatoarele MM linii sunt cate o pereche de numere a,ba, b, vrea ca punctele aa si bb sa fie unite pe desen.

Date de ieșire

DADA sau NUNU, depinde daca e posibil (vezi exemplu)

Restricții și precizări

  • 1N1051 \leq N \leq 10^5
  • 1Mmin(2105,N(N1)2)1 \leq M \leq min(2*10^5,\frac{N*(N-1)}{2})
  • 1a,bN1 \leq a, b \leq N, aba \neq b.
  • 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.

Log in or sign up to be able to send submissions!