题目描述

一个国家的 $N$ 个城市通过双向航线相连。

规定一次操作为：

• 选定其中一个城市
• 开设该城市到其它所有城市的航线，同时取消该城市的原有航线

请问是否存在一种操作方式，使得每两个城市之间都存在直达航线（操作次数不限）。

输入格式

第一行，一个整数 $N$，表示城市的数量。

第二行，一个整数 $M$，表示初始的航线数量。

接下来的 $M$ 行，每行两个不相等的整数，表示该航线连接的两个城市。

输出格式

若存在符合题意的操作方式，则输出 DA。否则输出 NE。

2
0

DA

3
2
1 2
2 3

NE

4
2
1 3
2 4

DA

提示

【样例 1 解释】

选定城市 $1$（即开通 $1-2$ 的航线）即可。

【样例 3 解释】

原有航线为 $1-3$ 和 $2-4$。

第一次选定城市 $1$。此时航线 $1-3$ 被取消，同时新开设航线 $1-1,1-2,1-4$。

第二次选定城市 $3$。此时新开设航线 $3-1,3-2,3-4$。

【数据规模与约定】

对于 $100\%$ 的数据，$2 \le N \le 1000$，$0 \le M \lt \dfrac{N(N-1)}{2}$。

【提示与说明】

题目译自 COCI 2016-2017 CONTEST #5 T4 Ronald。

本题分值按 COCI 原题设置，满分 $120$。