Problem Description

A country has $N$ cities connected by bidirectional flights.

An operation is defined as:

• Selecting one city
• Establishing flights from this city to all other cities, while canceling its existing flights

Determine if there exists a sequence of operations such that every pair of cities is directly connected by a flight (with no limit on the number of operations).

Input Format

The first line contains an integer $N$, representing the number of cities.

The second line contains an integer $M$, representing the initial number of flights.

The next $M$ lines each contain two distinct integers, indicating the two cities connected by a flight.

Output Format

If there exists a valid sequence of operations, output DA. Otherwise, output NE.

Sample Input and Output

Sample Input #1

2
0

Sample Output #1

DA

Sample Input #2

3
2
1 2
2 3

Sample Output #2

NE

Sample Input #3

4
2
1 3
2 4

Sample Output #3

DA

Notes

[Sample 1 Explanation]

By selecting city $1$ (establishing a flight from $1$ to $2$), the condition is met.

[Sample 3 Explanation]

The initial flights are between cities $1$ and $3$, and cities $2$ and $4$.

First, select city $1$. The flight $1-3$ is canceled, and new flights $1-1, 1-2, 1-4$ are established.

Next, select city $3$. New flights $3-1, 3-2, 3-4$ are established.

[Data Range and Constraints]

For $100\%$ of the data, $2 \le N \le 1000$, $0 \le M < \frac{N(N-1)}{2}$.

[Translation and Original Problem]

This problem is translated from COCI 2016-2017 CONTEST #5 T4 Ronald.

This problem is scored according to the original COCI settings, with a maximum score of $120$.

见题面 Input 部分

见题面 Output 部分