Guess the Initial Pair Set

This is an interactive problem.

You are given an integer \( n \) and an unknown collection \( S \) consisting of \( n \) unordered pairs \( (x, y) \) such that the numbers \( 1, 2, \ldots, 2n \) appear exactly once in \( S \). For example, when \( n=3 \), an example of a valid \( S \) is \( \{(1,5), (2,3), (4,6)\} \).

You do not know the initial \( S \). However, you are allowed to perform a type of operation. In each operation you choose two indices \( i, j \) (\( 1 \le i, j \le 2n \)). Then, the interactive judge will swap the positions of the integers \( i \) and \( j \) in the current set \( S \) (if \( i \) and \( j \) are in the same pair or if \( i=j \), nothing happens). Note that the pairs remain unordered. For example, if \( S = \{(1,5), (2,3), (4,6)\} \) and you perform the operation with \( i=2, j=6 \), then the positions are swapped so that \( S \) becomes \( \{(1,5), (6,3), (4,2)\} \) which is equivalent to \( \{(1,5), (2,4), (3,6)\} \).

After the initial configuration and after each operation, the judge reveals a value \[ res = \min_{(x,y) \in S} \max(x,y) \] that is, the minimum over all pairs of the maximum number in that pair.

Your task is to guess the initial set \( S \) (i.e. before any swap operation) within \( lim \) operations. Note that all operations you perform are permanent; the swaps are not reverted after each query. Also note that the initial \( S \) is fixed in advance (the interactor is non-adaptive).

Interaction

The interactor has multiple test cases within a single test file. The interaction for each test case is as follows:

1. The interactor first gives you two integers \( n \) (the number of pairs) and \( lim \) (the limit on the number of allowed operations).
2. Before any operation, the judge prints an integer \( res \) (as defined above).
3. You may then output a line in the format ^ i j (with a caret followed by the two indices) to perform an operation swapping numbers at positions \( i \) and \( j \).
4. After each such operation, the judge outputs a new value of \( res \).
5. When you decide to guess the initial set \( S \), output a line with ! and then output \( n \) lines, each containing two integers \( x \) and \( y \), representing the pairs in \( S \). The order of the pairs and the order of the numbers in each pair do not matter.

Important: Make sure that the total number of operations over all test cases in a test file does not exceed \( 2.5 \times 10^5 \), otherwise you may get a time limit error. You have at least 1 second time per test file and up to 384 MB of memory.

inputFormat

The input begins with an integer \( T \) representing the number of test cases. For each test case, the following occurs:

• An initial line with two integers \( n \) and \( lim \).
• Then, before any operation, the judge outputs an integer \( res \) (the value defined as \( \min_{(x,y)\in S} \max(x,y) \)).
• The remaining interaction involves reading responses after your swap operations and finally outputting your guess.

Note: In the offline simulation our sample test cases are set so that no swap operations are performed.

outputFormat

For each test case, when you decide to guess the initial set \( S \), output a line with ! followed by \( n \) lines, each containing two integers representing a pair in the initial set \( S \). Ensure that your output is flushed after each line.

sample

1
3 0
2

!
1 2
3 4
5 6

</p>