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 vertices, numbered with integers from to . 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 . On the device, there are lamps, the of which is connected to the vertex of the tree. For all , the lamp's light will turn on if there exists a vertex of the tree numbered where . Let's define as the distance between vertices and in tree, or the number of edges on the simple path between and .
Vasya wants to solve this quiz and guess the tree using operations with the device. Help him!
Interaction
You should implement the following procedure:
vector<int> find_tree(int n, int t)
: Number of vertices in the tree.
: Number of current subtask.
: This procedure is called exactly once, and should return a vector of integers. For integers , and should denote an edge between vertices and . 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)
: A vector of integers between and , denoting an operation on the device.
: This procedure returns an array of integers, where the integer is if the lamp of the vertex is on, and otherwise.
: This procedure can be called at most times.
It is guaranteed that in each test the tree is fixed beforehand and won't change depending on your program's operations.
Limits
.
Let 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 .
In subtask 2, you will receive the full 85 points if . If , you will receive points.