D. Simple Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay has an undirected tree with $$$n$$$ nodes, where each node is labeled from $$$1$$$ to $$$n$$$. Each node $$$u$$$ also has an associated integer value $$$val_u$$$. For each node $$$u$$$, determine the shortest distance to a node $$$v$$$ $$$(v \neq u)$$$ such that:$$$ \implies $$$ ($$$val_u$$$ $$$\&$$$ $$$val_v$$$) $$$ \neq $$$ $$$max(val_u , val_v)$$$.

___________________________________________________________

  • $$$\&$$$ represents the bitwise AND operation between two values.
  • $$$\max(a, b)$$$ represents the maximum of $$$a$$$ and $$$b$$$.
  • distance between two nodes is the number of edges in the shortest path between them in the tree.

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of nodes in the tree.
    • The second line contains $$$n$$$ integers $$$val_1, val_2, \dots, val_n$$$ $$$(1 \leq val_i \leq 10^9)$$$ — the integer values assigned to each node.
    • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$, representing an undirected edge in the tree.
  • The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$
Output
  • For each node $$$1$$$ to $$$n$$$ ,print the shortest distance to the node that satisfies the given condition. If no such node exists, print $$$-1$$$ for that node.
Example
Input
2
6
3 7 2 5 8 1
1 2
2 3
3 4
4 5
5 6
5
2 2 2 2 2
5 3
4 3
2 5
1 2
Output
1 1 1 1 1 1 
-1 -1 -1 -1 -1
Note
  • For Test Case $$$1$$$: For every node it's adjacent node satisfies the required condition.
  • For Test Case $$$2$$$: For each node there is no other node which satisfies the given condition.