제한된 교환으로 정렬하기

1부터 N까지의 수로 이루어진 순열이 주어진다. 한 번의 움직임에서는 미리 허용된 교환 중 하나를 골라, 지정된 두 위치에 있는 수를 서로 바꿀 수 있다.

목표는 가능한 한 적은 교환을 사용해 순열을 1, 2, 3, ..., N 순서로 만드는 것이다.

초기 순열과 사용할 수 있는 교환 목록이 주어질 때, 순열을 정렬하는 최단 교환 순서 하나를 출력하시오.

첫째 줄에 순열의 길이 N과 사용할 수 있는 교환의 수 M이 주어진다. (1 <= N <= 12, 1 <= M <= N*(N-1)/2)

둘째 줄에는 1부터 N까지의 수로 이루어진 순열이 주어진다.

셋째 줄부터 M개의 줄에는 사용할 수 있는 교환이 주어진다. 각 줄은 두 수 A와 B로 이루어져 있으며, 현재 A번째 위치와 B번째 위치에 있는 수를 서로 바꿀 수 있다는 뜻이다. 같은 교환 설명은 두 번 이상 주어지지 않는다.

첫째 줄에 사용한 교환의 수 X를 출력한다.

다음 X개의 줄에는 사용할 교환의 번호를 한 줄에 하나씩 출력한다. 입력에서 첫 번째로 주어진 교환이 1번이고, 이후 교환은 순서대로 번호가 하나씩 증가한다.

항상 답이 존재하는 입력만 주어진다. 최단 방법이 여러 가지라면 그중 아무거나 출력해도 된다.