print1622. Arrange

printArrange

Ограничения: время – 3s/6s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

“Arrange” is a planetary popular Flash game. In “Arrange” the player is given a permutation of numbers 1 to `N` and a list of allowed swaps. He then has to perform a sequence of swaps that transforms the initial permutation back to the ordered sequence `1,\ 2,\ 3,\ 4,\ 5,\ …,\ N`.
In order to break the high score list, you need to perform the minimal amount of swaps possible. You can't do that, but you can write a program that does it for you!
Input
The first line of input contains two integers, `N` (`1\ ≤\ N\ ≤\ 12`), the length of the initial sequence and `M` (`1\ ≤\ M\ ≤\ N*(N\ –\ 1)\ /\ 2`) number of allowed swaps. The second line of input contains a permutation of number 1 to `N`.
The next `M` lines contain descriptions of allowed swaps. If the line contains numbers `A` and `B` you are allowed to swap the `A`-th number with the `B`-th number. The input will never contain two identical swaps.
Note: the test data shall be such that the solution, not necessarily unique, will always exist.
Output
In the first line of input print the minimal number of swaps, `X`.
In the next `X` lines print the required swaps, in order. In each line print the index of the swap performed. Swaps are numbered increasingly as they appear in the input, starting from 1.

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
Source: COCI 2009/2010 contest #2
loading