Coloring
A coloring of an undirected graph T is a function C : V(T) → N where V(T) is a set of vertices of T. A coloring C is pretty if for every two vertices a and b they are connected with an edge if and only if |C(a) - C(b)| = 1.
You are given an undirected graph. Find some pretty coloring of this graph or report its nonexistence.
Input
The first line contains two integers n and m (1 ≤ n ≤ 2 * 10^5, 0 ≤ m ≤ 2 * 10^5): the number of vertices and the number of edges in the graph. Each of the next m lines contains two integers x and y (1 ≤ x, y ≤ n) which are the pair of vertices connected by the corresponding edge. Loops and multiple edges are not allowed.
Output
If a pretty coloring does not exist, print NET (no in Russian) on the single line of the output. Otherwise, print DA (yes in Russian) on the first line. On the next line, print n integers C(1), ..., C(n) for some pretty coloring C. The values of C(x) should satisfy the constraints 1 ≤ C(x) ≤ 10^9. If there are multiple possible answers, print any one of them.