对于非负整数 $k$，我们按如下方式递归定义 $k$-三元图（$k$-trostruki graf）：
如果一个图仅由一个顶点组成，则称其为 0-三元图。
对于 $k \ge 1$，如果一个图是由三个 $(k-1)$-三元图 $G, H$ 和 $I$ 组合而成，即从每个图中各选择一个顶点，并添加三条连接这些所选顶点的新边，则称该图为 $k$-三元图。
下图展示了一个 3-三元图。
你的任务是判断给定的输入图是否为某个 $k$ 的 $k$-三元图。
输入格式
第一行包含两个自然数 $N$ 和 $M$，分别表示图中的顶点数和边数。
接下来的 $M$ 行，每行包含两个自然数 $a$ 和 $b$ ($1 \le a, b \le N$)，表示顶点 $a$ 和 $b$ 之间的一条边。图中不存在自环，且不会重复列出同一条边。
输出格式
如果给定的图是某个 $k$ 的 $k$-三元图，则输出 da，否则输出 ne。
子任务
在所有子任务中，满足 $1 \le N \le 200\,000$ 且 $1 \le M \le 300\,000$。
| 子任务 | 分值 | 约束条件 |
|---|---|---|
| 1 | 15 | $N \le 10, M \le 20$ |
| 2 | 20 | $N \le 1000, M \le 2000$ |
| 3 | 15 | 若图为 $k$-三元图，保证其构造方式为：在每一步中，所选的三个顶点均是其对应低阶三元图中在上一层被选中的顶点。（始终选择“中间”顶点。） |
| 4 | 50 | 无附加约束。 |
样例
输入 1
3 3 1 2 2 3 3 1
输出 1
da
输入 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
输出 2
ne
输入 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
输出 3
da
说明 3
这是上图中图的“三分之一”，即一个 2-三元图。