Ограничения: время – 3s/6s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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 Input 2
3 2
2 1 3
1 3
2 3
Sample Input 3
5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5
Source: COCI 2009/2010 contest #2