## DMOPC '18 Contest 1 P5 - Sorting

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Java 2.5s
Python 2.5s
Memory limit: 256M

Author:
Problem type

You are considering a permutation of to and a non-negative integer . The elements at indices and may be swapped only if where denotes the XOR of and . However, has not yet been decided. What is the smallest possible non-negative integer so that this permutation may be sorted from least to greatest?

To make this more interesting, the permutation will be updated. You are given updates of the form u v meaning that and have been swapped. After each of the updates, what is the best ?

Note that the indices are 1-indexed, but the values are from to .

#### Constraints

For all , .
is a permutation, so each element from to will appear exactly once.

#### Input Specification

The first line will contain two space-separated integers, and .
The next line will contain space-separated integers, .
The following lines will each contain two space-separated integers, and , the indices to be swapped.

#### Output Specification

For each query, output a line containing a single non-negative integer, the smallest possible given the current permutation.

#### Sample Input 1

4 2
2 3 1 0
4 3
1 1

#### Sample Output 1

2
2

#### Explanation for Sample 1

After the first update, the permutation is . Swap and , then and .
The second update doesn't change anything.

#### Sample Input 2

4 3
1 0 2 3
1 2
3 4
1 4

#### Sample Output 2

0
1
2