Problem Background

Translated from COCI 2009.11 T5 "POSLOZI"

Given a permutation of length $N$ $(1 \le N \le 12)$. There are $M$ allowed modification methods $(1 \le M \le \frac{N \times (N-1)}{2})$, ensuring no duplicate methods. Each method is represented by $L$ and $R$, meaning you can swap the numbers at indices $L$ and $R$. You can modify the permutation multiple times. Please provide a modification scheme to transform the original permutation into $1, 2, 3, \ldots, N$. If there are multiple solutions, output the one with the fewest modifications. If there are still multiple solutions, output any one.

Problem Description

Input and Output Format

Input Format

The first line contains two integers $N$ and $M$.
The second line contains $N$ integers representing the permutation.
The next $M$ lines, each containing two integers, represent the $i$-th modification method.

Output Format

The first line contains an integer $\mathit{ope\_cnt}$, representing the minimum number of modifications.
The next $\mathit{ope\_cnt}$ lines, each containing an integer, represent the $i$-th modification.

Sample Input and Output

Sample Input #1

2 1
2 1
1 2

Sample Output #1

1
1

Sample Input #2

3 2
2 1 3
1 3
2 3

Sample Output #2

3
2
1
2

Sample Input #3

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

Sample Output #3

0

见题面 Input 部分

见题面 Output 部分