P10829 [COTS 2023] Ternary Graph Graf

Translated from [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D1T1. $\texttt{2s,0.5G}$. Happy birthday to NaCly_Fish! (2024.7.28).

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.

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$.

If $G$ is a $k$-ternary graph, output $\texttt{da}$ (Croatian for “yes”); otherwise output $\texttt{ne}$ (Croatian for “no”).

#### 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$. | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $15$ | $N \leq 10$, $M\le 20$ | | $2$ | $20$ | $N \leq 1000$, $M\le 2000$ | | $3$ | $15$ | Satisfies the special property | | $4$ | $50$ | No additional constraints | 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