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.
In other words, the unordered swap pairs will be pairwise distinct.
Subtask 1 [1/15]
Subtask 2 [2/15]
Subtask 3 [3/15]
For each , there are at most pairs of the form or , across all choices of .
Subtask 4 [9/15]
No additional constraints.
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 .
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.
4 4 4 2 3 1 1 2 2 3 3 4 4 1
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.