Dragon Seal

Problem Description

An immortal dragon attacked the Byteland. After days of battle, the heroes finally beat the dragon. However, the dragon is immortal such that it can not be killed, so the magicians in Byteland decide to seal the dragon using ancient black magic. The dragon is scheduled to be sealed under an undirected magic tree with $n$ vertices. In each vertice of the tree, there are two gems. Each gem has its magic value $m$ and power value $p$. The black magic requires removing exactly one gem from each vertex such that there will be exactly one gem remaining at each vertex. The total power is the sum of the power values of all the gems that remained in the tree. To escape from sealed, the dragon has a chance to attack. It will choose a target vertex on the tree, then select some vertices among it and its neighbor vertices, and finally start an attack on them. If at least one vertex is attacked, and the bitwise XOR sum among magic values of all the gems in attacked vertices is equal to zero, the tree will be broken, and the dragon escapes. The magicians must never let this happen. Please write a program to help them determine how to choose gems such that the dragon can never escape, and the total power is maximized.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case: The first line contains a single integer $n$ ($2\leq n\leq 60$), denoting the number of vertices. In the next $n$ lines, the $i$-th line contains four integers $m_i$, $p_i$, $m_i'$ and $p_i'$ ($1\leq m_i,m_i'<2^{64}$, $1\leq p_i,p_i'\leq 10^7$), describing the two gems in the $i$-th vertex. Each of the following $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i\leq n$, $u_i\neq v_i$), describing an undirected edge between the $u_i$-th vertex and the $v_i$-th vertex. It is guarenteed that the input is a tree.

Output

For each test case, output a single line containing an integer, denoting the total power to seal the dragon. When it is impossible to seal the dragon, please print ''$\texttt{-1}$'' instead.

Sample Input

2
2
3 1 3 1
3 2 3 2
1 2
3
1 3 2 1
2 2 4 3
1 3 3 2
1 2
2 3

Sample Output

-1
8

Source

2023“钉耙编程”中国大学生算法设计超级联赛（3）