P7763 [COCI 2016/2017 #5] Ronald

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.

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.

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

**[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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T4 Ronald_.** **The score of this problem follows the original COCI setting, with a full score of $120$.** Translated by ChatGPT 5