Boyama
Çoxrəngləmə istiqamətsiz qrafın T üçün C : V(T) → N funksiyası adlanır, burada V(T) - T-nin zirvələr çoxluğudur. C rəngləməsi yaxşı adlanır, əgər iki zirvə a və b arasında kənar varsa yalnız o halda |C(a) - C(b)| = 1.
İstiqamətsiz qraf verilib. Onun üçün yaxşı rəngləmə tapın və ya onun olmadığını bildirin.
Giriş məlumatları
Birinci sətir qrafda zirvələrin və kənarların sayını göstərən iki ədəd n və m (1 ≤ n ≤ 2 * 10^5, 0 ≤ m ≤ 2 * 10^5) ehtiva edir. Növbəti m sətirin hər biri iki ədəd x və y (1 ≤ x, y ≤ n) ehtiva edir - kənarla birləşdirilmiş zirvələr cütü. Döngələr və çoxkənarlar yoxdur.
Çıxış məlumatları
Əgər yaxşı rəngləmə mövcud deyilsə, ayrıca sətirdə NET (rusca yox) çıxarın. Əks halda, birinci sətirdə DA (rusca bəli) çıxarın. Növbəti sətirdə n tam ədəd C(1), ..., C(n) - yaxşı rəngləmə C çıxarın. C(x) dəyərləri 1 ≤ C(x) ≤ 10^9 məhdudiyyətlərinə cavab verməlidir. Əgər bir neçə rəngləmə mövcuddursa, onlardan hər hansı birini çıxarın.