Problem Description

Translated from COCI 2009.11 T5 “POSLOZI”.

You are given a permutation of length $N$ $(1 \le N \le 12)$. There are $M$ allowed types of operations $(1 \le M \le \frac{N \times (N - 1)}{2})$. It is guaranteed that no operation type is repeated. Each operation is described by $L$, $R$, meaning you may swap the number at index $L$ with the number at index $R$. You may apply operations to the permutation any number of times. Please output one sequence of operations that turns the original permutation into $1$, $2$, $3$, $\ldots$, $N$. If there are multiple solutions, output one with the minimum number of operations. If there are still multiple, output any one of them.

Input Format

The first line contains two integers $N$, $M$.
The second line contains $N$ integers, describing the permutation.
The next $M$ lines each contain two integers; the $i$-th line describes the $i$-th allowed operation.

Output Format

The first line contains an integer $\mathit{ope\_cnt}$, the minimum number of operations.
The next $\mathit{ope\_cnt}$ lines each contain one integer, indicating that you perform the $i$-th allowed operation.

2 1
2 1
1 2

1
1

3 2
2 1 3
1 3
2 3

3
2
1
2

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

0

Hint

Translated by ChatGPT 5