There are N people and M teams. Each team is a subset of N people.

For each team, we need to pick a captain. No people could be a captain of more than one team.

A person a is said to be a subordinate of a person b if there is some team including both a and b in which b is the captain.

A captain selection process is said to be valid if we could not find a sequence of more than 2 people a₁, a₂, ..., a_k such that ai is a subordinate of a_i+1 (i < k) and a_k is a subordinate of a₁.

For example, if we have 4 people and 3 teams:

Team 1: {1, 2, 3}
Team 2: {2, 3, 4}
Team 3: {3, 4, 1}

The captain selection process:

Captain 1: 1
Captain 2: 2
Captain 3: 4

is not valid since 1 is a subordinate of 4, 4 is a subordinate of 2 and 2 is a subordinate of 1.

Your job is to determine a valid captain selection process.

Input

The first line contains a number t (about 10), which is the number of test cases. Then t test cases follow. Each test case has the following form.

The first line contains two numbers N and M (1 ≤ N, M ≤ 50).

Each of the M teams is described in the next 2 lines. The first line contains the number of people in the team. Each team has either 2 or 3 people. The second line contains the indexes (1-based) of the people in that team.

There is a blank line after each test case's input.

Output

For each test case, print a number -1 if there is no valid captain selection process.

Otherwise, print M lines, each line contains the index of the captain of the corresponding team.

Print a blank line after each test case's output.

Example

Input:
2
4 3
3
1 2 3
3
2 3 4
3
3 4 1

4 3
3
1 2 3
2
2 4
3
3 4 2

Output:
-1

1
2
3