Dat je graf sa $N$ čvorova i $M$ grana. Da li možete da obojite čvorove grafa u najviše $1001$ boju tako svaka dva čvora između kojih postoji grana budu obojeni u različitu boju?

Opis ulaza

• Prva linija standardnog ulaza sadrži prirodne brojeve $N$ $(1\leq N\leq 3\cdot 10^5)$ i $M$ $(1\leq M \leq 3\cdot 10^5)$.
• Svaka od naredniih $M$ linija standardnog ulaza sadrže po dva prirodna broja $u$, $v$ $(1 \leq u, v \leq N, u \neq v)$ i označava da postoji grana između čvorova $u$ i $v$ u grafu.

Opis izlaza

• U prvoj liniji standardnog izlaza ispisati "$\texttt{DA}$" (bez navodnika) ako postoji bojenje koje zadovoljava uslov zadatka, inače ispisati "$\texttt{NE}$" (bez navodnika).
• U slučaju da postoji bar jedno bojenje koje zadovoljava uslov zadatka, u drugog liniji standardnog izlaza ispisati $N$ prirodnih brojeva u intervalu $[1, 1001]$, gde vrednost $i$-tog broja predstavlja redni broj boje $i$-tog čvora.

Primer ulaza

5 6
1 2
4 3
1 2
5 4
2 3
5 1

Primer izlaza

DA
1 1001 2 1001 5