The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains an integer n, which is the size of the tree. The vertices be indexed from 1.

On the next n-1 lines, each line contains two integers a,b, denoting there is an edge between a and b.

The next line contains an integer Q, denoting the number of the operations.

On the next Q lines, each line contains three integers t,a,b. t=1 means we reverse every edge’s color on path a to b. t=2 means we reverse every edge’s color adjacent to path a to b. t=3 means we query about the number of black edge on path a to b.

T<=5.

n,Q<=10^5.

Please use scanf,printf instead of cin,cout,because of huge input.