Planet Krypton is about to explode. The inhabitants of this planet have to leave the planet immediately. But the problem is that, still some decisions have to be made — where to go, how to go etc. So, the council of Krypton has invited some of the people to meet in a large hall. There are n people in planet Krypton, for sim- plicity they are given ids from 1 to n. The council uses a super computer — Oracle to call them in the meeting. Oracle has four types of messages for invitation. The message format is “type x y”, where x and y are two different person’s ids and type is an integer as follows • 1 • 2 • 3 • 4 x y means that either x or y should be present in the meeting. x y means that if x is present, then no condition on y, but if x is absent y should be absent. x y means that either x or y must be absent. x y means that either x or y must be present but not both. Each member of the council has an opinion too. The message format is “type x y”, where x, y and z are three different person’s ids and type is an integer as follows • 1 x y zmeansthatatleastoneofx,yorzshouldbepresent • 2 x y zmeansthatatleastoneofx,yorzshouldbeabsent Now you have to find whether the members can be invited such that every message by oracle and the council members are satisfied. Input Input starts with in integer T (≤ 200) denoting number of cases. Each case starts with a blank line. Next line contains 3 integers n, m and k (3 ≤ n ≤ 1000, 0 ≤ m ≤ 2000, 0 ≤ k ≤ 5) where m means the number of messages by oracle, k means the total members in the council. Each of the next m lines will contain a message of Oracle in the format given above. Each of the next k lines will contain a message of a council member. You can assume that all the ids given are correct. Output For each case, print the case number and whether it’s possible to invite the people such that all the messages are satisfied. If its not possible, then print ‘Impossible.’ in a single line. Otherwise, print ‘Possible’ and the number of invited people and the Ids of invited people in ascending order. Print the line leaving a single space between fields. Terminate this line with a ‘.’. See the samples for details. There can be multiple answers; print any valid one.
2/2 Sample Input 3 321 321 123 1123 441 221 412 413 414 2234 450 312 223 224 212 221 Sample Output Case 1: Possible 2 1 3. Case 2: Impossible. Case 3: Possible 0.