输入样例

3 
1 2 3 
1 2 
1 3 
2 
1 

Output

6 
9 
6 

顶点的权值均为正
1s, 128MiB for each test case.