DreamGrid has just found two trees, both consisting of n vertices, in his right pocket. Each edge in each tree has its own weight. The i-th edge in the first tree has a weight of , while the i-th edge in the second tree has a pair of weight, denoted by .

Let  be the -th vertex in the first tree, and  be the -th vertex in the second tree. Let  be the set containing the indices of all the edges on the path between the -th and the -th vertex in the first tree. Similarly, let  be the set containing the indices of all the edges on the path between the -th and the -th vertex in the second tree. Define the following values:

1. 
2. 
   
3. 
   

As DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index  is good, if for all  and , . Please help DreamGrid figure out all the valid indices.

You may have seen this problem before, but this time we need you to have an  solution, or it may not pass.

输入描述:

There are multiple test cases. The first line contains an integer , indicating the number of test cases. For each test case:

The first line contains an integer  indicating the number of vertices in both trees.

For the following  lines, the -th line contains three integers ,  and , , indicating that there is an edge, whose weight is , connecting vertex  and  in the first tree.

For the following  lines,the -th line contains four integers , ,  and  (, ), indicating that there is an edge, whose weight is , connecting vertex  and  in the second tree.

It's guaranteed that the sum of  of all test cases does not exceed .

输出描述:

For each test case output  integers (  is the number of valid indices) in one line separated by a space in increasing order, indicating the indices of the valid vertices.

Note that if there is no valid vertex, you should print ``-1'' instead.

2
2
1 2 1
1 2 2 3
4
1 2 7
1 3 8
1 4 12
1 2 8 8
2 3 9 7
2 4 6 4

-1
3 4