Stack Management (Large)

You are playing a solitaire game with $N$ stacks of face-up cards. Every stack starts with exactly $C$ cards. Each card has a value and a suit, and no two cards in the game share the same value and suit.

One move is one of the following.

1. If two or more cards of the same suit are on top of different stacks, you may remove the smallest-valued one of those cards from the game. A stack that loses its last card is still in play. It just becomes empty.
2. If some stack is empty, you may take the top card of any non-empty stack and put it on that empty stack, where it becomes the only card.

You win if some sequence of moves leaves every stack with at most one card. Given the starting arrangement, decide whether you can win.

The first line has one integer $P$, the number of premade stacks that the test cases draw from. Each of the next $P$ lines describes one premade stack. The $i$-th of those lines starts with $C_i$, the number of cards in the $i$-th premade stack, and continues with $C_i$ ordered pairs of integers. The $j$-th pair, $V_{ij}$ and $S_{ij}$, is the value and the suit of the $j$-th card from the top of that stack.

The next line has one integer $T$, the number of test cases. Each test case takes two lines. The first line has two integers $N$ and $C$, the number of stacks and the number of cards in each stack. The second line has $N$ integers $P_i$, the indexes of the premade stacks that form the board, numbered from 0.

For each test case, print one line of the form Case #x: y, where x is the test case number starting from 1, and y is POSSIBLE if you can win the game and IMPOSSIBLE if you cannot.

• $1 \le T \le 100$
• $2 \le P \le 60000$
• $0 \le P_i < P$
• $2 \le N \le 50000$
• $2 \le C \le 50000$
• $2 \le C_i \le 50000$
• $4 \le N \times C \le 10^5$
• $1 \le V_{ij} \le 50000$
• $1 \le S_{ij} \le 50000$
• The $P_i$-th premade stack has exactly $C$ cards.
• No two cards in a test case have the same value and suit.

In the first case of the sample there are two stacks of two cards each. The first stack has the 7 of suit 2 on top and the 7 of suit 1 below it. The second stack has the 3 of suit 2 on top and the 6 of suit 2 below it. One winning line is: remove the 3 of suit 2, then remove the 6 of suit 2, which empties the second stack, then move the 7 of suit 2 onto that empty stack. Every stack now holds at most one card.

In the second case of the sample there are three stacks of two cards each. The only legal move removes the 5 of suit 4, and no new move opens up after it.