Interactive Tree Reconstruction

This is an interactive problem.

dXqwq has an unrooted tree with \( n \) nodes, numbered from \(1\) to \( n \). You need to reconstruct its structure by asking a series of queries.

You can choose two integers \(1 \leq u,v \leq n\) and output ? u v as a query.

For each query, if the nodes on the unique path between \(u\) and \(v\) share a common node it will return that node's number; otherwise, it returns \(0\). (All returned numbers and formulas must be interpreted in \(\LaTeX\) style, for instance, \(0\) is given as \(0\)).

Your goal is to determine the tree structure using no more than \(147154\) queries. The tree is fixed in advance, so the interactive system is non-adaptive.

When you have determined the tree, output a line containing ! followed by \(n-1\) lines. Each of these lines should contain two integers \(u[i]\) and \(v[i]\) representing an edge of the tree. The order of the edges does not matter. Remember to flush the output after each line.

inputFormat

The input begins with a line containing two integers: id (the subtask identifier) and n (the number of nodes).

For offline testing, the next \(n-1\) lines provide two integers per line representing an edge of the tree.

outputFormat

First, output a line containing ! indicating the final answer.

Then output \(n-1\) lines, each line containing two integers representing an edge of the tree.

sample

1 2
1 2

!
1 2