CAPTAIN - Captain Selection

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 a1, a2, ..., ak such that ai is a subordinate of ai+1 (i < k) and ak is a subordinate of a1.

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

Added by:Jimmy
Date:2009-12-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Own problem

hide comments
2024-01-10 07:40:46 Oleg
Warning: broken test cases.
Printing -1 for all cases passes.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.