30953번 - Interactive Reconstruction 다국어인터랙티브

문제

This is an interactive task where your program will communicate with a grader through standard input and output. Your task is to reconstruct a labelled tree with $N$ nodes and $N-1$ edges. Nodes are labelled from 1ドル$ to $N$.

Your program is allowed to make a few queries of the following type: Your program should print a string of $N$ characters, consisting only of zeros and ones, one corresponding to each node. The grader will return a sequence of $N$ space-separated integers, the $i$-th representing the sum of the values (i.e. digits of the query string) of all neighbours of the $i$-th node. That is, if node $j$ is a neighbour of node $i,ドル then the $j$-th digit of the query string counts towards the sum in the $i$-th number of the grader's answer.

See the example below for an illustration.

입력과 출력

The first input line will contain the number $N,ドル the number of nodes in the tree.

Your program then has two options:

1. Print "QUERY" (without quotation marks), a space, and a string of $N$ zeros and ones.
2. Print "ANSWER" (without quotation marks), a newline, and $N - 1$ lines, each containing a pair of space-separated integers $a, b,ドル indicating that there exists an edge between nodes $a$ and $b$.

If your program prints a query, this will be followed by the grader returning a line with $N$ space-separated integers, one per node. If your program prints an answer, the grader will check the returned tree for correctness.

If there was a mistake in your queries, either due to incorrect formatting or due to an exceeded number of queries, the grader will immediately terminate.

Important: Ensure that your program flushes its output after printing and correctly exits after printing the answer.

입력

출력

제한

• 2ドル \leq N \leq 3\cdot 10^4$
• At most 2ドル \uparrow \uparrow 3 = 2^{(2^2)} = 16$ queries are allowed. The final answer does not count toward this restriction.

힌트

The tree in question is the following one:

1-4-2
 |
 5-3

With the three queries in the example, it is possible to reconstruct it uniquely.