{"raw_statement":[{"iden":"statement","content":"信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\\sim n$ 之间的编号。\n\n一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。\n\nAlenka 想知道是否有可能通过将且仅将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 `3 4 1 2`，那么圈可以从 `4` `1` 两个同学间断开；但是如果顺序是 `2 1 4 3`，那么没有一种合理的方式。\n\n在这一晚，Kreso 准备下达 $q$ 条指令。在每条指令中，他会要求两个学生交换位置。在每一次交换之后你需要帮助 Alenka 回答他的问题。\n"},{"iden":"input","content":"第一行包含两个整数 $n,q$，表示学生的数量和交换数。\n\n第二行包含 $n$ 个整数 $a_i$，描述第 $i$ 个位置的学生编号。\n\n在接下来的 $q$ 行中，每行两个整数 $x_i,y_i$，描述 Kreso 的第 $i$ 条指令，即标号 $x_i$ 的学生和标号 $y_i$ 的学生交换位置。"},{"iden":"output","content":"共 $q$ 行。\n\n在第 $i$ 行输出在第 $i$ 次交换后 Alenka 的问题的答案。\n\n如果答案是肯定的，输出 `DA`，否则输出 `NE`。"},{"iden":"note","content":"**【样例解释 #2】**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/382d6t5r.png)\n\n**【数据范围】**\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $15$ | $n,q \\leq 500$ |\n| $2$ | $20$ | $n,q \\leq 5000$ |\n| $3$ | $35$ | 无特殊性质 |\n\n对于 $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$。\n\n本题满分 $70$ 分。"}],"translated_statement":null,"sample_group":[["5 2\n2 3 4 5 1\n1 3\n3 1","NE\nDA"],["4 2\n2 3 1 4\n4 2\n3 4","NE\nDA"],["6 5\n2 1 5 6 3 4\n3 1\n3 4\n3 2\n4 5\n5 4","NE\nNE\nDA\nNE\nDA"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}