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.
1 mandy dinosaur jets jetsons jaqueline rhinocerous jets rockets hope rhinocerous jetsons rockets sandy platypus rockets
Please log in to submit your solution.
|Average test runtime||1.52|
|Points (changes over time)||10|
|Tried by||2 users|
|Solved by||2 users|