Let's call permutation (p_1, p_2, \ldots, p_n) splittable if it's possible to split it into two increasing subsequences so that every element goes to exactly one subsequence. For example, permutation (3, 1, 5, 2, 4) is splittable, as we can split it into two increasing subsequences and (1, 2, 4), while permutation (3, 2, 1) isn't splittable.
You are given a permutation (p_1, p_2, \ldots, p_n), and you must process queries. In the -th query, you have to swap elements p_{u_i}, p_{v_i}, and tell whether permutation is splittable.
Note that queries are not independent (each next query is applied to the result of applying previous queries, not to the initial permutation).
A sequence is a subsequence of a sequence if can be obtained from by deletion of several (possibly, zero or all) elements. For examples of what "can be split into two increasing subsequences" means, refer to the notes.
The first line of the input contains two integers (2 \le n \le 2\cdot 10^5, 1 \le q \le 2\cdot 10^5) — the length of the permutation and the number of queries correspondingly.
The -th of the next lines contains two integers u_i, v_i (1 \le u_i, v_i \le n, u_i \neq v_i), denoting that in the -th query, you have to swap elements p_{u_i}, p_{v_i}.
After each query, output YES, if the permutation is splittable, and NO if it's not.
You can print YES and NO in any case (e.g. the strings yEs, yes, Yes will be taken as a positive answer).
Example 1
After the first query, permutation becomes (2, 1, 3, 5, 4), which can be split into increasing subsequences (2, 3, 5) and .
After the second query, permutation becomes (2, 5, 3, 1, 4), which can't be split into two increasing subsequences.
After the third query, permutation becomes (2, 5, 1, 3, 4), which can be split into two increasing subsequences and (1, 3, 4).
After the fourth query, permutation becomes (4, 5, 1, 3, 2), which can't be split into two increasing subsequences.
After the fifth query, permutation becomes (4, 5, 1, 2, 3), which can be split into two increasing subsequences and (1, 2, 3).