For a non-negative integer $k$, we define the concept of a $k$-triple graph recursively as follows.

A graph is said to be 0-triple if it consists of exactly one vertex.

For $k \ge 1$, a graph is said to be $k$-triple if it is formed by taking three $(k-1)$-triple graphs $G$, $H$, and $I$, choosing one vertex from each of those three graphs, and adding three new edges connecting the chosen vertices.

The image below shows a 3-triple graph.

Your task is to determine, for a given input graph, whether it is $k$-triple for some $k$.

Input

The first line contains two natural numbers $N$ and $M$, representing the number of vertices and the number of edges in the graph, respectively.

Each of the following $M$ lines contains two natural numbers $a$ and $b$ ($1 \le a, b \le N$), which represent an edge between vertices $a$ and $b$. No edge connects a vertex to itself, and no edge will be listed twice.

Output

In a single line, print da if the given graph is $k$-triple for some $k$, and ne otherwise.

Subtasks

In all subtasks, $1 \le N \le 200\,000$ and $1 \le M \le 300\,000$.

Examples

Input 1

3 3
1 2
2 3
3 1

Output 1

da

Input 2

9 12
1 2
2 3
3 1
3 4
4 5
3 5
5 6
6 7
7 5
7 8
9 8
7 9

Output 2

ne

Input 3

9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
1 7
7 4
4 1

Output 3

da

Note

Explanation of the third example: This refers to "one third" of the graph from the image above, i.e., a 2-triple graph.