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