COCI '22 Contest 3 #2 Dirigent

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Winter school of informatics ends with a traditional dance. There are n students who participate. Each of them has a unique label between 1 and n.

First, conductor Krešo orders the students to form a circle such that each student holds hands with two other students.

Alenka is wondering if it is possible to break the circle by making exactly one pair of neighbouring students stop holding hands and that the newly formed sequence of students is sorted by their labels. For example, if their order is 3 4 1 2, then the circle can be broken between students with labels 4 and 1, but if their order is 2 1 4 3, then there is no way to break the circle in such a way.

During the night, Krešo is going to give q instructions. In each of them, he is going to order two students to swap places. After each swap, you need to help Alenka answer her question.

Input Specification

The first line contains two integers n and q (1 \le n, q \le 300\,000), the number of students and the number of swaps.

The second line contains n integers a_i (1 \le a_i \le n), describing the initial placement of students in the circle.

In each of the next q lines there are two integers x_i, y_i (1 \le x_i, y_i \le n, x_i \ne y_i), that describe Krešo's i-th instruction in which students with labels x_i and y_i swap places.

Output Specification

In the i-th of the q lines, output the answer to Alenka's question after i swaps have been carried out. If the answer is affirmative output DA; otherwise, output NE.


Subtask Points Constraints
1 15 n, q \le 500
2 20 n, q \le 5\,000
3 35 No additional constraints.

Sample Input 1

5 2
2 3 4 5 1
1 3
3 1

Sample Output 1


Sample Input 2

4 2
2 3 1 4
4 2
3 4

Sample Output 2


Explanation for Sample 2

Students in the beginning, after the first and after the second swap.

Sample Input 3

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

Sample Output 3



There are no comments at the moment.