Background

After carefully planning the workers’ moving routes and finishing all plans, you finally made money. You contracted a bigger mine pit and bought more advanced equipment.

However, after starting operation, you found that some mineral transport channels were installed in the wrong direction. Luckily, they can be reversed, and the central control system allows you to operate them easily.

But now the biggest problem is: you just took over this mine pit, and you do not even know what it looks like, let alone which switch corresponds to which transport channel.

Time is money. You want to figure out the whole structure of the mine pit and the mapping between all switches and channels as soon as possible.

Problem Description

This is an interactive problem.

Your mine pit has $n$ nodes, numbered $1\sim n$. They are connected by $n-1$ transport channels, forming a tree.

All transport channels are directed. For a transport channel from node $u$ to node $v$, all minerals produced at node $u$ or delivered to node $u$ can be transported to node $v$ at a faster speed. If a node has multiple outgoing transport channels, then these minerals will be evenly distributed among these channels.

The central control system contains $n-1$ switches and one monitor. The switches are numbered $1\sim n-1$. Each switch can be set to position $0$ or $1$. The $n-1$ switches correspond one-to-one with the $n-1$ transport channels, but you do not know their correspondence. You only know that, suppose the transport channel corresponding to switch $i$ was installed as from $u_i$ to $v_i$, then when the switch is set to $0$, its transport direction is the same as when it was installed; when the switch is set to $1$, its transport direction becomes from $v_i$ to $u_i$. Your monitor can observe, for each node, how many different nodes its arriving minerals come from, that is, how many nodes (including itself) can transport minerals to this node through transport channels.

After you adjust the switch positions, you need to wait for a while until the monitor result becomes stable, and only then is your reading meaningful. Therefore, to avoid wasting too much time, you hope to determine all the information you want within $50$ readings.

Input Format

At the beginning, you need to input a positive integer $n$. It is guaranteed that $2\le n \le 10000$.

After that, the input will generate readings based on your output. Each reading result is one line of $n$ positive integers, where the $i$-th integer indicates how many different nodes the minerals arriving at node $i$ come from.

In each test case, the connection structure of the mine pit and the initial directions of all transport channels when they were installed are fixed, meaning they will not be dynamically changed into another scheme that is also consistent with all previous answers because of your output.

Output Format

When you need to adjust the switches and wait for a reading, output a line ? s, where s is a 01 string of length $n-1$, and the $i$-th character indicates the position of switch $i$. Then the interactive library will provide, on your standard input, the reading result after the monitor becomes stable. You may read at most $50$ times.

When you already know all channel information, output a line ! u1 v1 ... un-1 vn-1, where $u_i,v_i$ indicate that the transport channel corresponding to switch $i$ was installed with direction from node $u_i$ to node $v_i$.

After outputting a line, you must flush the output buffer, otherwise the judging result may become TLE. The ways to flush the output buffer are:

• C：fflush(stdout);

• C++：fflush(stdout); or std::cout.flush(); or use std::endl for a newline

• Java：System.out.flush();

• Python：sys.stdout.flush()

5

1 4 1 2 3

1 1 2 3 4

? 0110

? 0000

! 1 4 2 3 2 4 4 5

Hint

The initial directions of the channels are shown in the figure above. The numbers on the channels represent the indices of the corresponding switches.

The sample is only used to explain the input/output format and the reading results, and does not mean that the answer can be derived from this reading.

The runtime and memory usage of the interactive library are not counted in the time and memory limits.

If you exceed the reading limit, the final answer is wrong, or the output format is wrong, the judging result will be WA.

Source and Acknowledgements

From the finals of THUPC2024 (Tsinghua University Student Programming Contest 2024 and Collegiate Invitational Contest). Thanks to THUSAA for providing this problem.

For testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository https://thusaac.com/public.

Translated by ChatGPT 5