//sj 가 아직

"정렬" 이라는 유명한 플래시게임이 있다.

"정렬" 게임에서 플레이어는 1 부터 N 까지의 임의로 나열된 순열을 받으며 허용되는 스왑(swap)의 리스트를 받는다. 그리고 플레이어는 허용되는 스왑들을 이용해서 초기의 순열을 1 부터 N 까지 순서로 다시 만들어야 한다. 최고점을 받기 위해서는 스왑을 최대한 적게 사용해야 한다.

사람은 그걸 못하겠지만 프로그램은 할 수 있으니 프로그램을 작성하여 플레이어를 도와주자.

입력

• 첫번째 줄에는 순열의 길이 N 과 허용된 스왑의 숫자 M 이 주어진다. (1 <= M <= N*(N+1)/2)
• 두번째 줄에는 초기 순열의 상태가 주어진다.
• 다음 M 줄 동안 허용된 스왑이 주어진다. 숫자 A 와 B 가 주어지면 순열의 A 번째와 B 번째 숫자를 바꿀 수 있다는 것이다.

출력

• 첫번째 줄에 게임에서 이기기 위한 최소 스왑의 개수를 출력한다.
• 두번째 줄부터 게임에서 이기기 위해 사용하는 스왑을 순서대로 출력한다. 스왑의 번호는 주어지는 순서대로 1부터 매겨진다.

입출력 예

input

2 1
2 1
1 2

output

1
1

input

3 2
2 1 3
1 3
2 3

output

3
2
1
2

input

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

output

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!

입력

• 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.

출력

• 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.

입출력 예

input

2 1
2 1
1 2

output

1
1

input

3 2
2 1 3
1 3
2 3

output

3
2
1
2

input

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

output

0

출처:COCI 2009/2010 contest2 5/6
번역:KangJ