Riolku's Mock CCC S3 - Mosey's Birthday

View as PDF

Submit solution

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

Problem type

For his birthday, his friends bought Mosey a permutation of the first N 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 M 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 M swaps they allowed him. Note that he can use each swap an arbitrary amount of times.


1 \le N \le 1\,000

0 \le M \le \frac{N(N-1)}{2}

a_i \ne a_j for all 1 \le i, j \le N

a_i \ne b_i for all 1 \le i \le N

(a_i, b_i) \ne (a_j, b_j) for any 1 \le i, j \le M

(a_i, b_i) \ne (b_j, a_j) for any 1 \le i, j \le M

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

Subtask 1 [1/15]

M = \frac{N(N-1)}{2}

Subtask 2 [2/15]

b_i = a_i+1 for all 1 \le i \le M

Subtask 3 [3/15]

For each 1 \le i \le N, there are at most 2 pairs of the form (i, j) or (j, i), across all choices of 1 \le j \le N.

Subtask 4 [9/15]

No additional constraints.

Input Specification

The first line will contain two integers, N and M.

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

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

Output Specification

On the first line, output K, the number of swaps you performed. K must satisfy 0 \le K \le 10^6. Note that K does not have to be minimal.

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

On the next K 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

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.


  • 4
    Riolku  commented on Feb. 19, 2021, 5:07 a.m.

    Data has been updated post-contest in order to prevent certain unintended solutions from passing.

    • 2
      DM__Oscar  commented on Feb. 20, 2021, 2:48 p.m.