Score : 1900 points
Snuke has found two trees A and B, each with N vertices numbered 1 to N. The i-th edge of A connects Vertex a_i and b_i, and the j-th edge of B connects Vertex c_j and d_j. Also, all vertices of A are initially painted white.
Snuke would like to perform the following operation on A zero or more times so that A coincides with B:
Determine if A can be made to coincide with B, ignoring color. If the answer is yes, find the minimum number of operations required.
You are given T cases of this kind. Find the answer for each of them.
Input is given from Standard Input in the following format:
T case_1 : case_{T}
Each case is given in the following format:
N a_1 b_1 : a_{N-1} b_{N-1} c_1 d_1 : c_{N-1} d_{N-1}
For each case, if A can be made to coincide with B ignoring color, print the minimum number of operations required, and print -1
if it cannot.
2 3 1 2 2 3 1 3 3 2 6 1 2 2 3 3 4 4 5 5 6 1 2 2 4 4 3 3 5 5 6
1 -1
3 8 2 7 4 8 8 6 7 1 7 3 5 7 7 8 4 2 5 2 1 2 8 1 3 2 2 6 2 7 4 1 2 2 3 3 4 3 4 2 1 3 2 9 5 3 4 3 9 3 6 8 2 3 1 3 3 8 1 7 4 1 2 8 9 6 3 6 3 5 1 8 9 7 1 6
6 0 7