Riolku's Mock CCC S3 - Mosey's Birthday

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

For his birthday, his friends bought Mosey a permutation of the first numbers. Excited to get such an amazing gift, Mosey starts to sort his array.

Before he can sort his array, his friends challenge him to sort it using only different types of swaps.

Mosey immediately points out that it might not be possible to sort the array, so his friends decide that they will be satisfied if Mosey can produce the lexicographically least possible output, using only the swaps they allowed him. Note that he can use each swap an arbitrary amount of times.

Constraints

for all

for all

for any

for any

In other words, the unordered swap pairs will be pairwise distinct.

for all

For each , there are at most pairs of the form or , across all choices of .

Input Specification

The first line will contain two integers, and .

The next line will contain space-separated integers, a permutation of the integers from to .

The next lines contain two integers each, and , indicating that you may swap the integers at positions and .

Output Specification

On the first line, output , the number of swaps you performed. must satisfy . Note that does not have to be minimal.

On the next line, output the lexicographically least possible permutation.

On the next lines, output the swap performed. It must be one of the allowed swaps.

Sample Input

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

Sample Output

3
1 2 3 4
3 2
1 4
3 2

Explanation for Sample Output

Note that it is not required that you output a sequence of moves of minimum length.