eolymp
bolt
Try our new interface for solving problems
Problems

Coloring

Coloring

Time limit 1 second
Memory limit 128 MiB

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 data

The first line contains two integers n and m (1n2 * 10^5, 0m2 * 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 (1x, yn) which are the pair of vertices connected by the corresponding edge. Loops and multiple edges are not allowed.

Output data

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 1C(x) ≤ 10^9. If there are multiple possible answers, print any one of them.

Examples

Input example #1
2 1
1 2
Output example #1
DA
1 2
Input example #2
3 3
1 2
2 3
3 1
Output example #2
NET
Input example #3
5 4
1 2
2 3
2 4
4 5
Output example #3
DA
1 2 1 3 4
Source 2013 Petrozavodsk, MIPT contest, August 25, Problem A