题目背景

译自 Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{2s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

题目描述

对于非负整数 $k$，我们递归地给出 $k-{}$三元图的定义。

• $k-{}$三元图是无向图。
• 对于 $k=0$，$k-{}$三元图 是一个仅包含 $1$ 个节点和 $0$ 条边的图。
• 对于 $k\gt 0$，$k-{}$三元图由三个 $(k-1)-{}$三元图组合而成。具体地说，在这三个 $(k-1)-{}$三元图中各选择一个节点，然后在这三个节点之间两两连边，得到的就是 $k-{}$三元图。

下图展示了一张 $3-{}$三元图。

给定无向图 $G$，判断它是否是 $k-{}$三元图。

输入格式

第一行，两个正整数，$N,M$，表示 $G$ 的点数和边数。

接下来 $M$ 行，每行两个正整数 $u,v$，表示 $G$ 中的一条边 $(u,v)$。

输出格式

如果 $G$ 是 $k-{}$三元图，输出 $\texttt{da}$（克罗地亚语「是」）；否则输出 $\texttt{ne}$（克罗地亚语「否」）。

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

提示

样例解释

样例 $3$ 解释：这是一张 $2-{}$三元图。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le N\le 200\, 000$，$0\le M\le 300\, 000$；
• $1\le u,v\le N$。

特殊性质：若 $G$ 是 $k-{}$三元图，保证每一步选择的 $3$ 个节点在之前已经被选中过。换句话说，总是选中「中间的节点」。