COCI '09 Contest 2 #5 Poslozi

View as PDF

Submit solution


Points: 40
Time limit: 1.5s
Memory limit: 64M

Problem types

"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, \dots, 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 Specification

The first line of input contains two integers, N (1 \le N \le 12), the length of the initial sequence and M (1 \le M \le \frac{N \times (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^\text{th} number with the B^\text{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 Specification

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

Comments

There are no comments at the moment.