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 a non-negative integer $k$, we define a $k$-ternary graph recursively.

• A $k$-ternary graph is an undirected graph.
• For $k=0$, a $k$-ternary graph is a graph with only $1$ node and $0$ edges.
• For $k>0$, a $k$-ternary graph is formed by combining three $(k-1)$-ternary graphs. Specifically, choose one node from each of the three $(k-1)$-ternary graphs, and then add edges between every pair of these three chosen nodes. The resulting graph is a $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, M$, representing the number of vertices and edges of $G$.

The next $M$ lines each contain two positive integers $u, 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”).

3 3
1 2
2 3
3 1

da

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

ne

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

da

Hint

Sample Explanation

Sample $3$ explanation: this is a $2$-ternary graph.

Constraints

For $100\%$ of the testdata, 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 at each step, the $3$ chosen nodes have already been chosen before. In other words, it always chooses the “middle nodes”.

Translated by ChatGPT 5