로널드

시간 제한1초메모리 제한64 MB

요약

N개 정점의 그래프에서 한 정점을 골라 그 정점에 붙은 모든 간선의 연결 상태를 뒤집는 연산을 반복할 때, 완전 그래프에 도달할 수 있는지 판정한다.

난이도: 어려움10점 중 9점
유형: 그래프, 비트 연산, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

한 나라에 도시가 $N$ 개 있고, 도시들은 양방향 항공편으로 연결되어 있다. 괴짜 항공사 사장 로널드 크럼프는 항공 일정을 자주 바꾼다. 정확히 말하면, 그는 매일 다음 작업을 한다.

도시 하나를 고른다.
그 도시에서 현재 항공편이 없는 다른 모든 도시로 항공편을 새로 만들고, 동시에 그 도시에서 출발하는 기존 항공편을 모두 없앤다.

예를 들어 도시 5에서 도시 1과 2로 가는 항공편은 있고 도시 3과 4로 가는 항공편은 없다면, 크럼프가 도시 5를 고른 뒤에는 도시 5에서 도시 3과 4로 가는 항공편이 생기고 도시 1과 2로 가는 항공편은 사라진다.

이 나라 시민들은 항공 일정이 완전해지는 날이 올 수 있는지 궁금해한다. 즉, 서로 다른 두 도시 사이마다 (직항) 항공편이 있는 날이다. 현재 항공 일정이 주어질 때, 이런 "완전한 날"이 올 수 있는지, 아니면 크럼프가 어떻게 바꾸든 절대 오지 않는지 판단하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 $N$ ( $2 \le N \le 1000$ )이 주어진다. 도시에는 1부터 $N$ 까지 번호가 붙어 있다.

둘째 줄에 현재 항공편의 수 $M$ ( $0 \le M < N(N-1)/2$ )이 주어진다.

다음 $M$ 개 줄에는 현재 항공편으로 연결된 두 도시의 번호가 한 줄에 하나씩 주어진다. 두 번호는 서로 다르다.

출력

완전한 날이 올 수 있으면 DA(크로아티아어로 "예"), 절대 오지 않으면 NE(크로아티아어로 "아니오")를 첫째 줄에 출력한다.

힌트

첫 번째 예제에서 크럼프는 첫날 (유일하게 가능한) 항공편 1-2를 만든다.

예제3

예제 1
입력
```
2
0
```
예상 출력
```
DA
```
예제 2
입력
```
3
2
1 2
2 3
```
예상 출력
```
NE
```
예제 3
입력
```
4
2
1 3
2 4
```
예상 출력
```
DA
```