Розфарбовка
Розфарбуванням неорієнтованого графа T називається функція C : V(T) → N, де V(T) - множина вершин графа T. Розфарбування C вважається хорошим, якщо між будь-якими двома вершинами a і b існує ребро лише тоді, коли |C(a) - C(b)| = 1.
Вам дано неорієнтований граф. Ваше завдання - знайти для нього хороше розфарбування або повідомити, якщо це неможливо.
Вхідні дані
Перша строка містить два числа n і m (1 ≤ n ≤ 2 * 10^5, 0 ≤ m ≤ 2 * 10^5): кількість вершин і кількість ребер у графі. Кожен з наступних m рядків містить два числа x і y (1 ≤ x, y ≤ n) - це пара вершин, з'єднаних ребром. Петлі та мультиребра відсутні.
Вихідні дані
Якщо хорошого розфарбування не існує, виведіть NET (ні українською) в окремому рядку. Інакше виведіть DA (так українською) в першому рядку. На наступному рядку виведіть n цілих чисел C(1), ..., C(n) - хороше розфарбування C. Значення C(x) повинні задовольняти обмеженням 1 ≤ C(x) ≤ 10^9. Якщо існує декілька можливих розфарбувань, виведіть будь-яке з них.