Problem Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D1T1. $\texttt{2s,0.5G}$.

Happy Birthday to NaCly_Fish! (2024.7.28)

Problem Description

For non-negative integers $k$, we recursively define the $k$-Ternary Graph.

• A $k$-Ternary Graph is an undirected graph.
• For $k=0$, the $k$-Ternary Graph is a graph containing only $1$ node and $0$ edges.
• For $k > 0$, the $k$-Ternary Graph is composed of three $(k-1)$-Ternary Graphs. Specifically, one node is selected from each of these three $(k-1)$-Ternary Graphs, and edges are added between each pair of these three nodes to form the $k$-Ternary Graph.

The figure below shows a $3$-Ternary Graph.

Given an undirected graph $G$, determine whether it is a $k$-Ternary Graph.

Input Format

The first line contains two positive integers, $N$ and $M$, representing the number of nodes and edges in $G$, respectively.

The next $M$ lines each contain two positive integers $u$ and $v$, representing an edge $(u, v)$ in $G$.

Output Format

If $G$ is a $k$-Ternary Graph, output $\texttt{da}$ (Croatian for "yes"); otherwise, output $\texttt{ne}$ (Croatian for "no").

Sample Input and Output

Input Sample #1

3 3
1 2
2 3
3 1

Output Sample #1

da

Input Sample #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 Sample #2

ne

Input Sample #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 Sample #3

da

Notes

Sample Explanation

Sample $3$ Explanation: This is a $2$-Ternary Graph.

Data Range

For $100\%$ of the data, it is guaranteed that:

• $1 \le N \le 200,000$, $0 \le M \le 300,000$;
• $1 \le u, v \le N$.

Special Property: If $G$ is a $k$-Ternary Graph, it is guaranteed that the three nodes chosen at each step have been selected before. In other words, the "middle node" is always chosen.

见题面 Input 部分

见题面 Output 部分