Раскраской неориентированного графа T называется функция C : V(T) → N, где V(T) - множество вершин T. Раскраска C называется хорошей, если между двумя вершинами a и b существует ребро только если |C(a) - C(b)| = 1.

Задан неориентированный граф. Найдите для него хорошую раскраску, или сообщите о ее отсутствии.

Входные данные

Первая строка содержит два числа n и m (1 ≤ n ≤ 2 * 105, 0 ≤ m ≤ 2 * 105): количество вершин и количество ребер в графе. Каждая из следующих m строк содержит два числа x и y (1 ≤ x, y ≤ n) - пара вершин, соединенные ребром. Петли и мультиребра отсутствуют.

Выходные данные

Если хорошей раскраски не существует, то вывести NET (нет по-русски) в отдельной строке. Иначе вывести DA(да по-русски) в первой строке. На следующей строке вывести n целых чисел C(1), ..., C(n) - хорошую раскраску C. Значения C(x) должны удовлетворять ограничениям 1 ≤ C(x) ≤ 109. Если существует несколько раскрасок, то вывести любую из них.