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, than
the circle can be broken between students with labels 4 and 1, but if their order is 2 1 4 3, than there is
no way to break the circle in such 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.

Subtask 1 (15 points): n, \(q \le 500\)

Subtask 2 (20 points): n, \(q \le 5\,000\)

Subtask 3 (35 points): No additional constraints.

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@@RISE_MATH_BLOCK_0@@i \le n\)), describing the initial placement of students in the
circle.
In each of the next \(q\) lines there are two integers \(x@@RISE_MATH_BLOCK_1@@i\) (\(1 \le x@@RISE_MATH_BLOCK_2@@i\)̸ = \(y\)\(i\)), that describe Krešo’s \(i-th\)
instruction in which students with labels \(x_{i}\) and \(y_{i}\) swap places.

In the \(i-th\) of the \(q\) lines outs put the answer to Alenka’s question after \(i\) swaps have been carried out. If
the answer is affirmative output DA, otherwise NE.

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 3