지휘자

겨울 정보학교는 전통 춤으로 마무리된다. 참가하는 학생은 $n$명이고, 각 학생에게는 $1$부터 $n$까지의 서로 다른 번호가 붙어 있다.

먼저 지휘자 크레시오가 학생들에게 원 모양으로 서서 각 학생이 양옆의 다른 두 학생과 손을 잡으라고 지시한다.

알렌카는 이웃한 학생 한 쌍만 손을 놓도록 해서 원을 끊었을 때, 새로 생긴 학생들의 줄이 번호순으로 정렬되어 있는지 궁금해한다. 예를 들어 학생들의 순서가 3 4 1 2이면 번호 4인 학생과 번호 1인 학생 사이에서 원을 끊을 수 있다. 순서가 2 1 4 3이면 이런 방식으로는 원을 끊을 방법이 없다.

밤사이 크레시오는 $q$개의 지시를 내린다. 각 지시에서는 두 학생이 자리를 맞바꾼다. 맞바꿀 때마다 알렌카의 질문에 답해야 한다.

첫 줄에 학생 수와 맞바꾸기 횟수인 두 정수 $n$과 $q$($1 ≤ n, q ≤ 300000$)가 주어진다.

둘째 줄에는 원에서 학생들이 처음 놓인 순서를 나타내는 $n$개의 정수 $a_i$($1 ≤ a_i ≤ n$)가 주어진다.

이어지는 $q$개의 줄에는 각각 두 정수 $x_i$, $y_i$($1 ≤ x_i, y_i ≤ n$, $x_i ≠ y_i$)가 주어진다. 이는 크레시오의 $i$번째 지시로, 번호가 $x_i$인 학생과 $y_i$인 학생이 자리를 맞바꾼다.

$i$번째 줄에는 처음 $i$번 맞바꾼 뒤의 답을 출력한다. 답이 가능하면 DA, 그렇지 않으면 NE를 출력한다.

두 번째 예제에 대한 설명이다. 처음 상태, 첫 번째 맞바꾼 후, 두 번째 맞바꾼 후의 학생 배치이다.