Conveyor Direction Determination

In the factory of JOI Co., Ltd., there are $$N$$ tables numbered from $$0$$ to $$N-1$$ and $$N-1$$ belt conveyors numbered from $$0$$ to $$N-2$$. For each belt conveyor $$i$$ (where $$0 \le i \le N-2$$), it connects table $$A_i$$ with table $$B_i$$. The belt conveyor transports products from one table to the other, but its direction is unknown. Ignoring the directions, the factory forms a connected network.

IOI-kun, the director of the factory, performs a sequence of operations to determine the original directions of all belt conveyors. In each operation, he proceeds as follows:

1. A subset of belt conveyors is selected, and their transport directions are reversed.
2. A subset of tables is chosen, and a product is placed on each selected table.
3. For every table that received a product, one of the following happens simultaneously:
   • If no belt conveyor is transporting products from that table, nothing happens.
   • If one or more conveyors are transporting products from that table, the product is moved by exactly one of them and stops at its destination.
4. IOI-kun checks every table. If a table has one or more products, he collects all of them.
5. For every belt conveyor whose direction was reversed in step 1, its direction is restored to its original state.

The goal is to determine the original direction of every belt conveyor by performing the above operations at most $$30$$ times.

Implementation Details:

You need to submit one file named conveyor.cpp (or the corresponding file in other languages). It should implement the following function and include conveyor.h via the preprocessing directive:

void Solve(int N, std::vector A, std::vector B);

This function is called once per test case with:

• N: the number of tables.
• A and B: arrays of length $$N-1$$ describing the connected tables for each conveyor.

You may call the following function to perform operations in the factory:

std::vector Query(std::vector<int> x, std::vector<int> y);

The parameters of Query are:

• x: an array of length $$N-1$$. For each i (where $$0 \le i \le N-2$$), if x[i] = 1 then the direction of conveyor i is temporarily reversed; if x[i] = 0, it is unchanged.
• y: an array of length $$N$$. For each j (where $$0 \le j \le N-1$$), if y[j] = 1 then a product is placed on table j, otherwise not.

This function returns an array z of length $$N$$ where for each table j, z[j] = 1 means that there is at least one product on table j, and z[j] = 0 means there is none.

After all necessary queries, use the following function exactly once to report the original directions:

void Answer(std::vector<int> a);

Here, the answer array a is of length $$N-1$$, and for each conveyor i, a[i] = 0 indicates it transports from A[i] to B[i], while a[i] = 1 indicates the reverse.

Important:

• The function Query must be called at most $$30$$ times.
• The arrays supplied to both Query and Answer must have the correct lengths and contain only 0s and 1s.
• The function Answer must be called exactly once.

Note: You are allowed to implement additional helper functions, use global variables, and output debugging information to standard error, but you must not use standard input or standard output for communicating with other files.

inputFormat

The function Solve receives the following inputs:

• An integer N representing the number of tables.
• A vector A of integers of length N-1, where each A[i] indicates one end of a conveyor.
• A vector B of integers of length N-1, where each B[i] indicates the other end of the corresponding conveyor.

Additionally, when you call the Query function, the arguments provided must adhere to the specified formats.

outputFormat

Your program should output the original directions of the conveyors by calling the Answer function exactly once with an array a of length N-1, where for each conveyor i:

• a[i] = 0 if the original direction is from A[i] to B[i],
• a[i] = 1 if the original direction is from B[i] to A[i].

sample

5
0 1 2 3
1 2 3 4

0 0 0 0