
Winter school of informatics ends with a traditional dance. There are
First, conductor Krešo orders the students to form a circle such that each student holds hands with two other students.
Alenka is wondering if it is possible to break the circle by making exactly one pair
of neighbouring students stop holding hands and that the newly formed sequence
of students is sorted by their labels. For example, if their order is
During the night, Krešo is going to give
Input Specification
The first line contains two integers
The second line contains
In each of the next
Output Specification
In the DA
; otherwise, output NE
.
Constraints
Subtask | Points | Constraints |
---|---|---|
No additional constraints. |
Sample Input 1
5 2
2 3 4 5 1
1 3
3 1
Sample Output 1
NE
DA
Sample Input 2
4 2
2 3 1 4
4 2
3 4
Sample Output 2
NE
DA
Explanation for Sample 2
Students in the beginning, after the first and after the second swap.

Sample Input 3
6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4
Sample Output 3
NE
NE
DA
NE
DA
Comments