Description

The $N$ cities of a country are connected by undirected air routes.

One operation is defined as:

• Choose one city.
• Open routes from this city to all other cities, and at the same time cancel all existing routes of this city.

Determine whether there exists a sequence of operations (with no limit on the number of operations) such that in the end, there is a direct route between every pair of cities.

Input Format

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

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

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

Output Format

If there exists a sequence of operations that satisfies the requirement, output DA. Otherwise, output NE.

2
0

DA

3
2
1 2
2 3

NE

4
2
1 3
2 4

DA

Hint

[Sample 1 Explanation]

It is enough to choose city $1$ (that is, open the route $1-2$).

[Sample 3 Explanation]

The original routes are $1-3$ and $2-4$.

Choose city $1$ for the first time. Then route $1-3$ is cancelled, and new routes $1-1,1-2,1-4$ are opened.

Choose city $3$ for the second time. Then new routes $3-1,3-2,3-4$ are opened.

[Constraints]

For $100\%$ of the testdata, $2 \le N \le 1000$, $0 \le M \lt \dfrac{N(N-1)}{2}$.

[Notes]

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

The score of this problem follows the original COCI setting, with a full score of $120$.

Translated by ChatGPT 5