strangedevice2

Strange Device

Vasya enjoys solving quizzes. He found a strange device and wants to know how it works.

This device is encrypted with a tree (a connected undirected graph without cycles) with \(n\) vertices, numbered with integers from \(1\) to \(n\). To solve this quiz you should guess this tree.

Fortunately, this device contains one operation, using which you should guess the cipher. You can give the device an array of non-negative integers \(d_1, d_2, \ldots, d_n\). On the device, there are \(n\) lamps, the \(i^{th}\) of which is connected to the \(i^{th}\) vertex of the tree. For all \(i\), the \(i^{th}\) lamp's light will turn on if there exists a vertex of the tree numbered \(j \neq i\) where \(dist(i, j) \leq d_j\). Let's define \(dist(i, j)\) as the distance between vertices \(i\) and \(j\) in tree, or the number of edges on the simple path between \(i\) and \(j\).

Vasya wants to solve this quiz and guess the tree using \(\leq K\) operations with the device. Help him!

Interaction

You should implement the following procedure:

vector<int> find_tree(int n, int t)

• \(n\): Number of vertices in the tree.
• \(t\): Number of current subtask.
• \(t\): This procedure is called exactly once, and should return a vector \(V\) of \(2n - 2\) integers. For integers \(0 \leq i < n - 1\), \(V[2i]\) and \(V[2i + 1]\) should denote an edge between vertices \(V[2i]\) and \(V[2i + 1]\). These edges should form a tree, which is equal to the hidden tree.

The above procedure can make calls to the following procedure:

vector<int> device_operation(vector<int> d)

• \(d\): A vector of \(n\) integers between \(0\) and \(n - 1\), denoting an operation on the device.
• \(t\): This procedure returns an array of \(n\) integers, where the \(i^{th}\) integer is \(1\) if the lamp of the \(i^{th}\) vertex is on, and \(0\) otherwise.
• \(t\): This procedure can be called at most \(1000\) times.

It is guaranteed that in each test the tree is fixed beforehand and won't change depending on your program's operations.

Limits

\(n = 1000\).
Let \(k\) be the largest number of operations used, among all testcases within the respective subtask.
In subtask 1, you will receive the full 15 points if \(k \leq K\).
In subtask 2, you will receive the full 85 points if \(k \leq K\). If \(K < k \leq 1000\), you will receive \(85\frac{K}{k}\) points.

Subtask #	Score	Constraints
1	15	\(K = 1000\)
2	85	\(K = 80\)

Samples

Sample Input 1	Sample Output 1
5 2 00000 11011 11100 10010	? 0 0 0 0 0 ? 1 1 2 0 2 ? 0 0 0 1 0 ? 0 1 0 0 1 ! 4 2 1 5 3 4 4 1

In this input example, the tree encrypting the device is:

The table of pairwise distances between the vertices of the tree is:

• If you make an operation \(d = [0,0,0,0,0]\), no lamp will switch on, because \(dist(i, j) > 0\) for all \(i \neq j\).
• If you make an operation \(d = [1,1,2,0,2]\), all lamps except the lamp of the \(3^{rd}\) vertex will switch on. For example, the lamp of the \(1^{st}\) vertex will switch on, because \(dist(1, 5) = 1 \leq 2 = d_5\).
• If you make an operation \(d = [0,0,0,1,0]\), all lamps except the lamps of the \(4^{th}\) and \(5^{th}\) vertices will switch on.
• If you make an operation \(d = [0,1,0,0,1]\), only the lamps of the \(1^{st}\) and \(4^{th}\) vertices will switch on.