Marbles in a Row

We will play the following game. We have N colored marbles, numbered from 1 to N. The marbles are placed next to each other on a wooden base with N positions, which are also numbered from 1 to N. The goal of the game is to arrange the marbles in the correct order: marble 1 should be in position 1, marble 2 in position 2, and so on.

To achieve this, we can apply a series of moves. There are M possible moves, and each of them is described by two numbers (a_i, b_i), where 1 ≤ i ≤ M. The move (a_i, b_i) swaps the marbles at positions a_i and b_i. Find the sequence with the fewest possible moves to win the game!

For example, let N=3, and initially, the marbles are in the order 2, 1, 3, as shown in the diagram below. Let there also be M=2 possible moves: (1, 3) and (2, 3).

We can win the game with the following sequence of 3 moves:

• Initial     2, 1, 3
• Move 1   3, 1, 2   swap positions (1, 3)
• Move 2   3, 2, 1   swap positions (2, 3)
• Move 1   1, 2, 3   swap positions (1, 3)

There is no way to win the game with fewer than 3 moves.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that will determine how to win T such games. For each game, it will read the initial position of the marbles and the allowed moves and print the minimum number and sequence of moves required to win.

Input File:

The input file named marbles.in is a text file with the following structure. The first line contains two integers, separated by a single space: the number of games T and the number of marbles N for each game. Then follow the descriptions of the T games, each with the following structure.

The first line contains an integer M: the number of allowed moves. The second line contains N integers, separated in pairs by a single space: the initial placement of the marbles in order from position 1 to position N. Each of the next M lines contains two integers, separated by a single space: the positions (a_i, b_i) to be swapped in this move.

Output File:

The output file named marbles.out is a text file with the following structure. It should contain the answer for each of the T games, in order. If there is a solution with a minimum number of moves K ≤ 0 for a game, the first line of the answer should contain the word "MOVES" and the number of moves K, separated by a single space. The next K lines should contain the numbers of the K moves required to win the game. If there are multiple solutions with the same minimum value of K for a game, your program can print any of them. If there is no solution for a game, the answer for that game should contain a line with the word "IMPOSSIBLE".

Example of Input - Output File

STDIN (marbles.in)

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

STDOUT (marbles.out)

MOVES 3
1
2
1
MOVES 1
1
MOVES 0
IMPOSSIBLE

Explanation: We need to answer about T=4 games, each with N=3 marbles. The first game is the one shown in the diagram on the previous page, where M=2. In the second game, where M=1, only one move is needed to place the last two marbles in the correct order. In the third game, where M=1, the marbles are already in the correct order from the beginning, so no move is required. Finally, in the fourth game, where again M=1, the only allowed move swaps the marbles in positions 1 and 3. There is no way to move the marble with number 3 that is in position 2, so this game has no solution.

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 12
• 1 ≤ M ≤ N×(N-1)/2
• For each allowed move, 1 ≤ a_i < b_i ≤ N.
• The list of allowed moves for each game will contain each move at most once.
• For test cases with a total value of 40%, N ≤ 5.
• For test cases with a total value of 80%, N ≤ 10.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 256 MB.