luogu#P9757. [COCI2022-2023#3] Dirigent

[COCI2022-2023#3] Dirigent

题目描述

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

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

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

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

输入格式

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

第二行包含 nn 个整数 aia_i,描述第 ii 个位置的学生编号。

在接下来的 qq 行中,每行两个整数 xi,yix_i,y_i,描述 Kreso 的第 ii 条指令,即标号 xix_i 的学生和标号 yiy_i 的学生交换位置。

输出格式

qq 行。

在第 ii 行输出在第 ii 次交换后 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】

【数据范围】

子任务 分值 特殊性质
11 1515 n,q500n,q \leq 500
22 2020 n,q5000n,q \leq 5000
33 3535 无特殊性质

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

本题满分 7070 分。