Tree Subsets#529

Tree Subsets

You are given a rooted tree with vertices. The root of the tree is vertex .

Each vertex has a value a_i, which is either or .

For each size (1 \le k \le n), determine which xor values can be obtained by choosing a set of vertices that satisfies the following conditions:

The value of a set is defined as the xor of the values of all vertices in this set: \bigoplus_{v \in S} a_v.

The subtree of vertex is the set of all vertices such that vertex lies on the simple path from the root to vertex .

The xor operation for bits is defined as follows: 0 \oplus 0 = 0, 0 \oplus 1 = 1, 1 \oplus 0 = 1, 1 \oplus 1 = 0.

The child of vertex is a vertex whose parent is .

Input

The first line contains one integer (1 \le t \le 1000) — the number of test cases.

Each test case consists of three lines.

The first line of each test case contains one integer (2 \le n \le 4 \cdot 10^5) — the number of vertices in the tree.

The second line contains integers a_1, a_2, \ldots, a_n (a_i \in \{0, 1\}) — the values of the vertices.

The third line contains n-1 integers p_2, p_3, \ldots, p_n (1 \le p_i < i), where p_i is the parent of vertex .

It is guaranteed that the sum of over all test cases does not exceed 4 \cdot 10^5.

Output

For each test case, output one line with integers ans_1, ans_2, \ldots, ans_n.

For each :

  • ans_k = 0, if among all valid sets of size only xor can be obtained;

  • ans_k = 1, if among all valid sets of size only xor can be obtained;

  • ans_k = 2, if among all valid sets of size both xor and xor can be obtained.

Examples

Example 1

Loading
Loading

Note

This is what the trees in the first and second test cases look like, respectively.

Consider the first test case.

For k = 1, both xor values can be obtained. For example, the set S = \{5\} is valid and has xor . And the set S = \{3\} is also valid and has xor . Therefore, ans_1 = 2.

For k = 3, both xor values can also be obtained. For example, the set S = \{2, 3, 5\} is valid because together with vertex all vertices in its subtree are chosen. Its xor is a_2 \oplus a_3 \oplus a_5 = 0 \oplus 1 \oplus 0 = 1. And the set S = \{3, 4, 5\} is also valid because together with vertex all vertices in its subtree are chosen. Its xor is a_3 \oplus a_4 \oplus a_5 = 1 \oplus 1 \oplus 0 = 0. Therefore, ans_3 = 2.

Thus, the answer for the first test case is .

Consider the second test case.

In this test case, both xor values can be obtained only for k = 6.

For example, the set S = \{3, 4, 6, 7, 8, 9\} is valid. Its xor is a_3 \oplus a_4 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 = 0 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 1.

And the set S = \{4, 5, 6, 7, 8, 9\} is also valid. Its xor is a_4 \oplus a_5 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 = 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 0. Therefore, ans_6 = 2.

Thus, the answer for the second test case is 1\ 0\ 1\ 0\ 1\ 2\ 0\ 0\ 0.

Scoring

A leaf is a vertex that has no children.

A bamboo is a tree in which every vertex has at most one child.

  1. ( points): \sum n \le 20;

  2. ( points): p_i=1;

  3. ( points): \sum n^3 \le 10^8;

  4. ( points): \sum n^2 \le 10^8;

  5. ( points): the total number of leaves over all test cases does not exceed ;

  6. ( points): after removing vertex , each component is a bamboo, and there are at most two such components;

  7. ( points): after removing vertex , each component is a bamboo;

  8. ( points): all trees are full binary trees, that is, n = 2^q - 1 for some integer , and for every vertex i > 1 we have p_i = \left\lfloor \frac{i}{2} \right\rfloor;

  9. ( points): n \le 2 \cdot 10^5 for each test case;

  10. ( points): no additional constraints.