题目描述

信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\sim n$ 之间的编号。

一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。

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

在这一晚，Kreso 准备下达 $q$ 条指令。在每条指令中，他会要求两个学生交换位置。在每一次交换之后你需要帮助 Alenka 回答他的问题。

输入格式

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

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

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

输出格式

共 $q$ 行。

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

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

5 2
2 3 4 5 1
1 3
3 1

NE
DA

4 2
2 3 1 4
4 2
3 4

NE
DA

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

NE
NE
DA
NE
DA

提示

【样例解释 #2】

【数据范围】

对于 $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$ 分。