Background

Watch your step when walking—don’t play with your phone while walking, or you might fall into the water.

When going out to have fun, pay attention to the weather—don’t swing on a swing on rainy days, or you might catch a cold.

Problem Description

This is an interactive problem and only supports C++ submissions.

Sanagi has a hidden positive integer array $a_0,\dots,a_{n-1}$ ($1\leq a_i\leq 10^9$). For a tree $T$ whose vertex set is $0\sim n-1$, define its diameter $D(T)$ as follows: when we assign vertex $i$ the weight $a_i$, $D(T)$ is the maximum, over all paths, of the sum of vertex weights on that path.

You need to determine at least $n-2$ of the values $a_i$ within 2000 queries and 2000 guesses:

• Query: Provide a tree $T$, and the interactive library returns $D(T)$. This operation is offline, meaning you only learn all query answers after you finish all queries.
• Guess: Provide a tree $T$ and a positive integer $x$, and the interactive library returns $[D(T)=x]$. This operation is online, meaning you learn the result immediately after each guess.

Implementation Details

You need to include the header haru.h.

You must implement the following function:

std::vector<int> haru(int n);

Here $n$ is the length of the array $a$.

This function should return an array $b$ of length $n$, where at most $2$ entries may be $-1$ to indicate you cannot determine the corresponding $a_i$. All other entries must be within $[1,10^9]$ and represent values of $a_i$ that you have determined.

This function may be called multiple times within a single test case.

You may call the following two functions:

std::vector<long long> query(const std::vector<std::vector<int>> &U,const std::vector<std::vector<int>> &V);

This corresponds to Query in the statement, and it can only be called once. You must ensure that $U$ and $V$ have the same length (denote it by $k$), and each element is an array of length $n-1$ containing only integers in $[0,n-1]$.

This function returns an array of length $k$, where the $i$-th value is $D(T)$ for the tree $T$ formed by edges $(U_{i,j}, V_{i,j})$ for $0\le j < n-1$.

bool guess(const std::vector<int> &U, const std::vector<int> &V, long long x);

This corresponds to Guess in the statement. You must ensure that $U$ and $V$ both have length $n-1$ and contain only integers in $[0,n-1]$.

This function returns a boolean indicating whether $D(T)$ for the tree $T$ formed by edges $(U_i, V_i)$ for $0\le i < n-1$ is equal to $x$.

You can check the provided grader.cpp, whose implementation is almost identical to the interactive library used in judging.

How to Run the Testing Program

The provided haru.cpp is a reference solution. You can compile your code in this problem directory using:

g++ grader.cpp haru.cpp -o haru -O2 -std=c++14 -static

For the compiled program, the input format is:

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains a positive integer $n$;
• The second line contains a length-$n$ positive integer array representing the hidden $a_i$.

The program will output scoring information. Specifically:

• If your input is invalid, or you violate certain limits during calls, you will receive Wrong Answer[x], and the program will terminate immediately. See the provided grader for details.
• Otherwise, the interactive library will output AC with x query(s) and y guess(es)., meaning you produced correct answers for every test case, and the maximum numbers of queries and guesses used are $x$ and $y$ respectively.

Constraints

This problem uses bundled tests.

For all data, it is guaranteed that: $10\leq n\leq 500$, $\sum n\leq 5\times 10^4$, $1\leq a_i\leq 10^9$.

Scoring

Notes:

• Contestants should not obtain internal information from the interactive library by illegal means, such as trying to access the array $a$ or interacting with standard I/O; such behavior is considered cheating.
• The interactive library is non-adaptive, i.e., the answers are fixed from the start and will not change based on your queries.

Under legal usage, the interactive library is guaranteed to use at most 1s time and 64MB memory.

This problem is first subject to the same limits as traditional problems: for example, a compilation error results in 0 points for the whole problem; runtime error, time limit exceeded, memory limit exceeded, etc. result in 0 points for the corresponding test(s), etc. Contestants may only access variables they define and those provided by the interactive library and their corresponding memory space; attempting to access other memory may cause compilation or runtime errors.

On this basis, suppose the full score of this test is $T$, the number of queries is $X$, and the number of guesses is $Y$. Then the score you can obtain for this test is $\lfloor T f(X) g(Y) \rfloor$, where:

$$ f(x) = \max\left(0,1-\left(\dfrac{\max(x-501,0)}{1500}\right)^{0.4}\right) $$

$$ g(x)=\max\left(0,\min\left(1,1.5-\left(\dfrac{\max(x-16,0)}{128}\right)^{0.2}\right)\right) $$

Here are some single-point values of $f(x)$ you may use:

Here are some single-point values of $g(x)$ you may use: