Sorting with Restricted Swaps

A game gives you a permutation of the numbers from 1 to N. In one move, you may use one of the allowed exchanges to swap the numbers at two specified positions.

Your goal is to transform the permutation into increasing order, 1, 2, 3, ..., N, using as few exchanges as possible.

Given the initial permutation and the list of exchanges that may be used, output any shortest sequence of exchanges that sorts the permutation.

The first line contains the length of the permutation, N, and the number of allowed exchanges, M. (1 <= N <= 12, 1 <= M <= N*(N-1)/2)

The second line contains a permutation of the numbers from 1 to N.

Each of the next M lines contains two numbers, A and B, meaning that you may swap the numbers currently in positions A and B. No exchange description appears more than once.

First output the number of exchanges used, X.

Then output X lines. Each line must contain the index of an exchange to use. The first exchange in the input has index 1, and the following exchanges are numbered in order.

Only inputs for which an answer exists are given. If there are multiple shortest sequences, output any one of them.