Sorting with Restricted Swaps

Time limit1sMemory limit128 MB

Summary

Find the minimum number of allowed position-swaps needed to sort a permutation of up to 12 elements, using BFS over permutation states.

Level: Medium7 of 10
Topics: BFS, Brute force, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1
Input
```
2 1
2 1
1 2
```
Expected output
```
1
1
```
Example 2
Input
```
3 2
2 1 3
1 3
2 3
```
Expected output
```
3
2
1
2
```

Example 3

Input

Expected output