You are given a tree with N nodes. Every node is colored with one color: white, red or blue.  For every edge in tree, cutting this edge will get two smaller parts. If one of two smaller parts has no red node and the other one has no blue node, the edge is "valuable".
It is guaranteed that there is at least one red node and one blue node.
You need to find the number of "valuable" edges.

The first line will be an integer \(T (1 \leq T \leq 10)\), which is the number of test cases.   
For each test data: 
The first line contains an integer N \((1 \leq N \leq 10^5 )\) — the number of nodes.
The next N-1 lines contain two integers a and b \((1 \leq a,b \leq N)\), which means there is an edge between node a and b.
Then the next one line contains n  integers, the i-th integer \(p_i (p_i = 0,1,2)\) indicates the color of node i. If \(p_i = 0\), the node is white. If \(p_i = 1\), the node is red. If \(p_i = 2\), the node is blue.

For each case, contains one line,  print the number of these edges.

3
4
1 2
2 3
2 4
1 0 0 2
5
1 2
2 3
3 4
4 5
2 0 0 0 1
3
1 2
2 3
1 2 1

2
4
0