Chef is given a tree with N nodes and a positive integer K. Each node is assigned a value A_{i}. 

Chef has to divide the tree into a forest of exactly K trees, numbered from 1 to K, such that each node belongs to exactly one tree.  
Let B_{i} denote the [bitwise XOR] of the values of all nodes belonging to the i^{th} tree.  

Find the maximum possible value of B_{1} \& B_{2} \& \dots \& B_{K}, where \& denotes the [bitwise AND operation].

------ Input Format ------ 

- The first line contains a single integer T, the number of test cases.
- Each test case consists of multiple lines:
- The first line contains two space-separated integers N and K — the number of nodes in the tree and a positive integer as mentioned in the statement, respectively.
- The next line contains N space-separated integers A_{1},A_{2},\ldots,A_{N}, the values assigned to each node. 
- The next (N-1) lines describe the edges. The i^{th} of these (N-1) lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between nodes u_{i} and v_{i}.

------ Output Format ------ 

For each test case, print a single integer, the maximum possible value of B_{1} \& B_{2} \& \dots \& B_{K}

------ Constraints ------ 

$1 ≤ T ≤ 5 \cdot 10^{4}$
$1 ≤ K ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
$1 ≤u_{i}, v_{i} ≤N$, $(u_{i}\neq v_{i})$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$. 

----- Sample Input 1 ------ 
2
6 2
1 4 2 2 1 5
1 2
1 3
2 4
2 5
3 6
8 3
1 13 5 14 2 9 0 8
1 2
1 3
1 4
2 5
3 6
3 7
6 8
----- Sample Output 1 ------ 
6
4
----- explanation 1 ------ 
Test case $1$: A possible way of dividing the nodes into $2$ trees is $[1,3,6]$ and $[2,4,5]$.
- $B_{1} = A_{1}\oplus A_{3}\oplus A_{6} = 1\oplus 2\oplus 5 = 6$
- $B_{2} = A_{2}\oplus A_{4}\oplus A_{5} = 4\oplus 2\oplus 1 = 7$

Thus, $B_{1}$ $\&$ $B_{2} = 6$ $\&$ $7 = 6$.  
Note that this is the maximum possible value of $B_{1}$ $\&$ $B_{2}$ you can obtain.  
Another way of dividing is $[1,2,4,5]$ and $[3,6]$, which leads to the same answer.
 
Test case $2$: A possible way of dividing the nodes into $3$ trees is $[1,3,6,7,8]$, $[4]$, and $[2,5]$
- $B_{1} = A_{1}\oplus A_{3}\oplus A_{6}\oplus A_{7}\oplus A_{8} = 1\oplus 5\oplus 9 \oplus 0\oplus 8 = 5$
- $B_{2} = A_{4} = 14$
- $B_{3} = A_{2}\oplus A_{5} = 13\oplus 2 = 15$.

Thus, $B_{1}$ $\&$ $B_{2}$ $\&$ $B_{3} = 5$ $\&$ $14$ $\&$ $\&$ $15 = 4$.  
Note that this is the maximum possible value of $B_{1}$ $\&$ $B_{2}$ $\&$ $B_{3}$ you can obtain.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Sorting

Complete search

Tree algorithms

Data structures
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)
inp = lambda : list(map(int, input().split()))

def dfs(p, prev, x):
	global c
	subtree = a[p - 1]
	for i in child[p]:
		if i == prev:
			continue
		subtree ^= dfs(i, p, x)
	if c != k - 1 and subtree & x == x:
		c += 1
		return 0
	return subtree

def check(x):
	global c
	(c, ans) = (0, 0)
	last = dfs(1, -1, x)
	if c == k - 1:
		if last & x == x:
			return True
	return False

def answer():
	ans = 0
	for i in range(30, -1, -1):
		if check(ans | 1 << i):
			ans |= 1 << i
	return ans
for T in range(int(input())):
	(n, k) = inp()
	a = inp()
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append(v)
		child[v].append(u)
	print(answer())