Hide

Problem B
Councilling

Each resident of a particular town is a member of zero or more clubs and also a member of exactly one political party. Each club is to appoint one of its members to represent it on the town council so that the number of council members belonging to any given party does not equal or exceed half the membership of the council. The same person may not represent two clubs; that is there must be a 1-1 relationship between clubs and council members. Your job is to select the council members subject to these constraints.

Input

In the first line of input there will be an integer $T \le 12$, giving the number of test cases.

Each of the $T$ testcases begins with a line with the number of residents $n$, $1 \leq n \leq 1\, 000$. The next $n$ lines each contain a resident, a party, the number of clubs the resident belongs to (at most $110$) and the names of such clubs. Each resident appears in exactly one input line.

Output

For each test case, follow the following format: Each line should name a council member followed by the club represented by the member. If several answers are possible, any will do. If no council can be formed, print “Impossible.” in a line. There will be a blank line in between two test cases.

Sample Input 1 Sample Output 1
2
4
fred dinosaur 2 jets jetsons
john rhinocerous 2 jets rockets
mary rhinocerous 2 jetsons rockets
ruth platypus 1 rockets
4
fred dinosaur 2 jets jetsons
john rhinocerous 2 jets rockets
mary rhinocerous 2 jetsons rockets
ruth platypus 1 rockets
fred jetsons
john jets
ruth rockets

fred jetsons
john jets
ruth rockets
Sample Input 2 Sample Output 2
1
1
fred dinosaur 2 jets jetsons
Impossible.

Please log in to submit a solution to this problem

Log in