在一个国家有 $N$ 个城市，它们之间通过双向航线相连。一位疯狂的航空公司总裁 Ronald Krump 经常修改航班计划。更具体地说，他每天都会进行以下操作：

• 选择其中一个城市；
• 在该城市与所有当前未与之建立航线的其他城市之间开设航线，同时取消该城市所有已有的航线。

例如，如果城市 5 与城市 1 和 2 之间存在航线，但与城市 3 和 4 之间没有航线，那么在 Krump 修改后，城市 5 与城市 3 和 4 之间将存在航线，而与城市 1 和 2 之间将不再有航线。

这个国家的居民想知道，是否会有那么一天，航班计划变得“完全”。换句话说，任意两个不同的城市之间都存在（直达）航线。

编写一个程序，根据当前的航班计划，判断是否可能达到这样一个“完全航线日”，或者无论 Krump 做出什么操作，这都永远不会发生。

输入格式

输入的第一行包含整数 $N$（$2 \le N \le 1000$），表示城市的数量。城市用 $1$ 到 $N$ 的数字编号。

第二行包含整数 $M$（$0 \le M < N(N-1)/2$），表示当前的航线数量。

接下来的 $M$ 行，每行包含两个不同的数字，表示当前相连的两个城市的编号。

输出格式

输出的唯一一行必须包含 DA（克罗地亚语中的“是”）或 NE（克罗地亚语中的“否”）。

样例

输入样例 1

2
0

输出样例 1

DA

输入样例 2

3
2
1 2
2 3

输出样例 2

NE

输入样例 3

4
2
1 3
2 4

输出样例 3

DA

说明

• 第一个样例的解释：在第一步中，Krump 将引入（唯一可能的）航线 1-2。
• 第三个样例的解释：如果 Krump 首先选择城市 1，那么将存在航线 1-2、1-4 和 2-4。如果他接着选择城市 3，航班计划将变得完全。