题目描述

You are playing a solitaire game in which there are $\mathbf{N}$ stacks of face-up cards, each of which initially has $\mathbf{C}$ cards. Each card has a value and a suit, and no two cards in the game have the same value/suit combination.

In one move, you can do one of the following things:

1. If there are two or more cards with the same suit that are on top of different stacks, you may remove the one of those cards with the smallest value from the game. (Whenever you remove the last card from a stack, the stack is still there — it just becomes empty.)
2. If there is an empty stack, you may take a card from the top of any one of the non-empty stacks and place it on top of (i.e., as the only card in) that empty stack.

You win the game if you can make a sequence of moves such that eventually, each stack contains at most one card. Given a starting arrangement, determine whether it is possible to win the game.

输入格式

The first line of the input gives the number $\mathbf{P}$ of premade stacks that will be used in the test cases. Then, $\mathbf{P}$ lines follow. The i-th of those lines begins with an integer $\mathbf{C}_{\mathbf{i}}$, the number of cards in the i-th of those premade stacks, and continues with $\mathbf{C}_{\mathbf{i}}$ ordered pairs of integers. The j-th of these ordered pairs has two integers $\mathbf{V}_{\mathbf{i j}}$ and $\mathbf{S}_{\mathbf{i j}}$, representing the value and suit of the j-th card from the top in the i-th premade stack.

Then, there is another line with one integer $\mathbf{T}$, the number of test cases. $\mathbf{T}$ test cases follow. Each case begins with one line with two integers $\mathbf{N}$ and $\mathbf{C}$: the number of stacks, and the number of cards in each of those stacks. Then, there is one line with $\mathbf{N}$ integers $\mathbf{P}_{\mathbf{i}}$, representing the indexes (starting from 0) of the test case's set of premade stacks.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is POSSIBLE if it is possible to win the game, or IMPOSSIBLE otherwise.

5
2 7 2 7 1
2 6 4 7 4
2 3 2 6 2
2 4 2 10 2
2 5 4 7 3
2
2 2
0 2
3 2
4 1 3

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

提示

Sample Explanation

In sample case #1, there are two stacks, each of which has two cards. The first stack has a 7 of suit 2 on top and a 7 of suit 1 below that. The second stack has a 3 of suit 2 on top and a 6 of suit 2 below that.

It is possible to win the game as follows:

• Remove the 3 of suit 2 from the second stack.
• Remove the 6 of suit 2 from the second stack. This makes the second stack empty.
• Move the 7 of suit 2 to the second stack. Then the win condition is satisfied: all stacks have at most one card.

In sample case #2, there are three stacks, each of which has two cards. It is not possible to win the game in this case; the only possible move is to remove the 5 of suit 4 on top of the third stack, and this does not open up any new moves.

Limits

• $1 \leq T \leq 100$.
• $2 \leq P \leq 60000$.
• $0 \leq P_i < P$, for all $i$.
• The $P_i$-th premade stack has exactly $C$ cards.
• No two cards in a test case have the same value/suit combination.

Small dataset (10 Pts, Test Set 1 - Visible)

• $2 \leq N \leq 4$.
• $2 \leq C_i \leq 13$, for all $i$.
• $2 \leq C \leq 13$.
• $1 \leq V_{ij} \leq 13$, for all $i$ and $j$.
• $1 \leq S_{ij} \leq 4$, for all $i$ and $j$.

Large dataset (30 Pts, Test Set 2 - Hidden)

• $2 \leq N \leq 50000$.
• $2 \leq C_i \leq 50000$, for all $i$.
• $2 \leq C \leq 50000$.
• $4 \leq N \times C \leq 10^5$.
• $1 \leq V_{ij} \leq 50000$, for all $i$ and $j$.
• $1 \leq S_{ij} \leq 50000$, for all $i$ and $j$.