Master of Connected Component

You have two trees $T_a$ and $T_b$, and they both have n nodes. All $n$ nodes on each tree are respectively labelled by integers in ranges $[1, n]$. The shape and label scheme of these two trees may be different. And you have a graph $G$ with $m$ nodes and all $m$ nodes on grape $G$ are respectively labelled by integers in ranges $[1, m]$. There are no edges in graph $G$ in the beginning, but every node on trees stores an edge of graph $G$.

For each index $ i $, it corresponds to node $ i $ in tree $T_a$, and node $i$ in tree $T_b$. There is a path from node $ i $ to the root of tree $T_a$, and there is a path from node $i$ to the root of tree $T_b$. Each path contains some nodes on trees, and each node stores an edge in graph $G$. All the nodes in both paths store some edges in graph $G$. For each index $i$, we temporarily add all these edges to graph $G$ and construct a new graph $G��$ . Now you are supposed to answer how many connected components are there in $G��$ . Of course, one single node with no edge is seemed as a connected component.

It is guaranteed that the root of each tree is labelled by number $1$.

The first line contains an integer $T (1 \leq T \leq 25)$ representing the number of test cases.

For each test case, the first line contains two integers $ n (1 \leq n \leq 10000), m (1 \leq m \leq 10000) $, representing the number of nodes of each tree and the number of nodes of graph G.

Next $n + n - 1$ lines describe tree $T_a$.

The following $n$ lines each contains two integers $u_i , v_i$ , representing that the node with lable $ i $ of tree $T_a$ refers to the undirected edge $(u_i , v_i)$ in graph $G$.

The following $n - 1$ lines each contains two integers $u_i , v_i$ , representing an edge $(u_i , v_i) $ in tree $T_a$, and the node $u_i$ is the father of node $v_i$.

Next $n + n - 1$ lines describe tree $ T_b$.

The following $n$ lines each contains two integers $u_i , v_i$ , representing that the node with lable $ i $ of tree $T_b$ refers to the undirected edge $ (u_i , v_i)$ in graph $ G $.

The following $n - 1$ lines each contains two integers $u_i , v_i$ , representing an edge $(u_i , v_i)$ in tree $T_b$, and the node $u_i$ is the father of node $v_i$ .
All $ u_i , v_i $ mentioned above satisfies $ 1 \leq u_i , v_i \leq m $

For each test case, print $ n $ lines, the $ i$-th line contains an integer refers to the answer of index $i$.

2
3 4
1 2
2 3
3 4
1 2
1 3
1 3
2 4
3 4
1 2
2 3
2 100
100 99
99 98
1 2
97 96
95 94
1 2

2
1
1
98
96

For first test case, the tree $T_a$ and tree $T_b$ look like following photos:

2017�й���ѧ��������ƾ���-����վ-����������л�㽭������