P9757 [COCI 2022/2023 #3] Dirigent

信息学冬令营以一场传统舞蹈结营。一共有 $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`。

**【样例解释 #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$ 分。