Each resident of a town that shall rename nameless 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-to-1 relationship between clubs and council members. Your job is to select the council members subject to these constraints.


In the first line of input there will be an integer \(t\) that defines the number of test cases to follow. 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.


For each test case, output either Possible if there is a valid assignment of residents to the council, or Impossible if there isn't.

Sample Input


mandy dinosaur jets jetsons
jaqueline rhinocerous jets rockets
hope rhinocerous jetsons rockets
sandy platypus rockets

Sample Output


This is challenge 10511 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.


Difficulty (1 vote)
Average test runtime 1.52
Points (changes over time) 10
Tried by 2 users
Solved by 2 users

Global ranking

# Name Runtime Points worth
1 Mac 1.50 10
2 Dark 1.53 10