Magnetic Gold Medals

A bookworm is arranging his n gold medals. He discovered that all medals are magnetic. Formally, each medal has a magnetic pole (and there are many kinds of poles). When two medals are placed next to each other, they attract if their poles are different and repulse if their poles are the same.

The bookworm does not know the pole of each medal. He can only determine whether two medals have the same or different poles by bringing them close together. In other words, you are allowed to perform at most Q interactive queries. For each query you choose two indices x and y (medals are numbered from 0 to n-1), and the interactive system returns whether medals x and y attract or repulse. A return value of 1 means they attract (i.e. their poles differ) while 0 means they repulse (i.e. their poles are the same).

The goal is to arrange all n medals into a permutation such that every pair of adjacent medals attract each other. If a valid arrangement exists, output any one valid permutation; otherwise, output -1. Note: This is an interactive problem. For the purpose of offline simulation and testing, an extra line is provided for each test case containing n integers that represent the magnetic pole types of the medals. When performing a query between medals x and y, you may internally compare these values: if the poles are different then they attract, otherwise they repulse. Also, if there is any magnetic pole that appears more than \( \lceil n/2 \rceil \) times (when \(n > 1\)), then it is impossible to arrange the medals as required.

Interactive Protocol:

• The first line of input contains an integer \(T\), the number of test cases.
• For each test case, the first line contains two integers \(n\) and \(Q\), indicating the number of medals and the maximum number of queries allowed.
• Then, an extra line is given with \(n\) integers representing the magnetic pole of each medal. (This line is only for offline simulation.)
• If you want to ask a query, output two integers \(x\) and \(y\) (separated by a space) and flush the output. Then, read an integer \(ret\) from input where \(ret = 1\) means the medals attract and \(ret = 0\) means they repulse.
• If you determine that no valid arrangement exists, output a line containing -1 and flush the output.
• If you find a valid arrangement, output a line containing \(n\) followed by a line with a valid permutation (indices separated by spaces), and flush the output.
• After processing all \(T\) test cases, terminate your program immediately.

inputFormat

The input begins with an integer \(T\) (the number of test cases). For each test case, the first line contains two integers \(n\) and \(Q\). The next line contains \(n\) integers, representing the magnetic pole of each medal. (This additional line is provided for offline testing simulation.)

outputFormat

For each test case, if a valid arrangement exists that ensures every pair of adjacent medals attract (i.e. have different magnetic poles), then first output a line containing \(n\) followed by a line containing the permutation of medal indices (0-indexed) separated by spaces. If no such arrangement exists, output a single line containing -1.

sample

1
3 10
1 2 1

3
0 1 2