{"problem":{"name":"[COCI 2022/2023 #3] Dirigent","description":{"content":"信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\\sim n$ 之间的编号。 一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。 Alenka 想知道是否有可能通过将且仅将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 `3 4 1 2`，那么圈可以从 `4` `1` 两个同学间断开；","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9757"},"statements":[{"statement_type":"Markdown","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\n## Input\n\n第一行包含两个整数 $n,q$，表示学生的数量和交换数。\n\n第二行包含 $n$ 个整数 $a_i$，描述第 $i$ 个位置的学生编号。\n\n在接下来的 $q$ 行中，每行两个整数 $x_i,y_i$，描述 Kreso 的第 $i$ 条指令，即标号 $x_i$ 的学生和标号 $y_i$ 的学生交换位置。\n\n## Output\n\n共 $q$ 行。\n\n在第 $i$ 行输出在第 $i$ 次交换后 Alenka 的问题的答案。\n\n如果答案是肯定的，输出 `DA`，否则输出 `NE`。\n\n[samples]\n\n## Note\n\n**【样例解释 #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$ 分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9757","tags":["2022","COCI（克罗地亚）"],"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"]],"created_at":"2026-03-03 11:09:25"}}