围圈圈

题目描述

有 $n$ 个人，每个人都有分别有一个 $1\sim n$ 之间的编号。

一开始，所有人围成一个圈，使得每个人都与另外两个人拉着手。

你想知道是否有可能通过将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 3 4 1 2，那么圈可以从 4 1 两个同学间断开；但是如果顺序是 2 1 4 3，那么没有一种合理的方式。

在这一晚，袁老师下达 $q$ 条指令。在每条指令中，他会要求两个学生交换位置。在每一次交换之后你需要做出判断。

输入格式

第一行包含两个整数 $n,q$，表示学生的数量和交换数。

第二行包含 $n$ 个整数 $a_i$，描述第 $i$ 个位置的学生编号。

在接下来的 $q$ 行中，每行两个整数 $x_i,y_i$，描述 袁老师的第 $i$ 条指令，即标号 $x_i$ 的学生和标号 $y_i$ 的学生交换位置。

输出格式

共 $q$ 行。

在第 $i$ 行输出在第 $i$ 次交换后的答案。

如果答案是肯定的，输出 DA，否则输出 NE。

样例 #1

样例输入 #1

5 2
2 3 4 5 1
1 3
3 1

样例输出 #1

NE
DA

样例 #2

样例输入 #2

4 2
2 3 1 4
4 2
3 4

样例输出 #2

NE
DA

样例 #3

样例输入 #3

6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4

样例输出 #3

NE
NE
DA
NE
DA

提示

【样例解释 #2】

【数据范围】

子任务	分值	特殊性质
$1$	$15$	$n,q \leq 500$
$2$	$20$	$n,q \leq 5000$
$3$	$35$	无特殊性质

对于 $100\%$ 的数据，满足 $1\leq n,q \leq 3\times10^5,1\le a_i\le n, 1\le x_i,y_i\le n,x_i\neq y_i$。

本题满分 $70$ 分。