Problem C
Councilling
Input: Standard Input

Output: Standard Output

 

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 nominate 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, giving the number of test cases. The next line will be blank. Each of the T test cases consists of up to 1000 lines, each naming a resident, a party, and a list of clubs to which the resident belongs. Names are alphanumeric and separated by a single space. Each resident appears in exactly one input line. Input lines do not exceed 80 characters. Every set of input ends with a blank 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 the word "Impossible." in a line. There will be a blank line in between two test cases.

 

Sample Input                               Output for Sample Input

2
 
fred dinosaur jets jetsons
john rhinocerous jets rockets
mary rhinocerous jetsons rockets
ruth platypus rockets
 
fred dinosaur jets jetsons
john rhinocerous jets rockets
mary rhinocerous jetsons rockets
ruth platypus rockets
 
fred jetsons
john jets
ruth rockets
 
fred jetsons
john jets
ruth rockets

 


Problemsetter: G. V. Cormack