Ronald

A country has $N$ cities connected by two-way air links. Ronald Krump, an eccentric airline president, often changes the flight schedule. More precisely, every day he does the following:

• He chooses one of the cities.
• He introduces flights from that city to every other city it currently has no flight to, and at the same time cancels every existing flight from that city.

For example, if city 5 has flights to cities 1 and 2 but not to cities 3 and 4, then after Krump chooses city 5, it has flights to cities 3 and 4 but not to cities 1 and 2.

The citizens want to know whether a day can come when the flight schedule is complete, that is, when a (direct) flight exists between every two different cities. Write a program that, given the current flight schedule, determines whether such a Complete Day is possible, or whether it never happens no matter which moves Krump makes.

The first line contains the integer $N$ ($2 \le N \le 1000$), the number of cities. The cities are labeled with the numbers 1 to $N$.

The second line contains the integer $M$ ($0 \le M < N(N-1)/2$), the number of current flights.

Each of the next $M$ lines contains two different numbers: the labels of two cities that are currently connected.

Print a single line containing DA (Croatian for "yes") if a Complete Day is possible, or NE (Croatian for "no") if it never happens.

In the first sample, Krump introduces the (only possible) flight 1-2 on the first day.