Riolku's Mock CCC S3 - Mosey's Birthday - Olympiads Online Judge

Riolku's Mock CCC S3 - Mosey's Birthday

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 $N$ ~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$ ~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$ ~M~ swaps they allowed him. Note that he can use each swap an arbitrary amount of times.

Constraints

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

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

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

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

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

$(a_i, b_i) \ne (b_j, a_j)$ ~(a_i, b_i) \ne (b_j, a_j)~ for any $1 \le i, j \le M$ ~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}$ ~M = \frac{N(N-1)}{2}~

Subtask 2 [2/15]

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

Subtask 3 [3/15]

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

Subtask 4 [9/15]

No additional constraints.

Input Specification

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

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

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

Output Specification

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

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

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

Sample Input

Sample Output

Explanation for Sample Output

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

Comments

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.

:(