카드 더미 정리 (라지)

앞면이 보이게 쌓인 카드 더미 $N$개로 혼자 하는 카드 게임을 한다. 각 더미에는 처음에 카드가 정확히 $C$장씩 있다. 카드마다 숫자와 무늬가 있으며, 숫자와 무늬가 모두 같은 카드는 게임 안에 둘 이상 없다.

한 번의 이동으로 다음 중 하나를 할 수 있다.

1. 무늬가 같은 카드가 서로 다른 더미의 맨 위에 두 장 이상 있으면, 그중 숫자가 가장 작은 카드를 게임에서 없앨 수 있다. 마지막 카드를 잃은 더미도 그대로 남는다. 빈 더미가 될 뿐이다.
2. 빈 더미가 있으면, 비어 있지 않은 더미 하나의 맨 위 카드를 가져와 그 빈 더미에 올릴 수 있다. 그 카드는 그 더미의 유일한 카드가 된다.

이동을 적절히 이어서 모든 더미에 카드가 한 장 이하만 남게 하면 이긴다. 처음 배치가 주어질 때, 이길 수 있는지 판정한다.

첫째 줄에 테스트 케이스가 사용하는, 미리 만들어 둔 더미의 개수 $P$가 주어진다. 다음 $P$개 줄에는 미리 만들어 둔 더미가 한 줄에 하나씩 주어진다. 그중 $i$번째 줄은 $i$번째 더미의 카드 장수 $C_i$로 시작하고, 이어서 정수 쌍이 $C_i$개 주어진다. $j$번째 쌍 $V_{ij}$와 $S_{ij}$는 그 더미의 위에서 $j$번째 카드의 숫자와 무늬이다.

다음 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에는 더미의 개수 $N$과 한 더미의 카드 장수 $C$가 주어진다. 둘째 줄에는 판을 이루는 더미의 번호 $P_i$가 $N$개 주어지고, 번호는 0부터 센다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 이길 수 있으면 POSSIBLE, 이길 수 없으면 IMPOSSIBLE이다.

• $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$
• $P_i$번째 더미의 카드 장수는 정확히 $C$이다.
• 한 테스트 케이스 안에서 숫자와 무늬가 모두 같은 카드는 둘 이상 없다.

예제의 첫 테스트 케이스에는 카드가 두 장씩인 더미가 둘 있다. 첫 더미는 위에 무늬 2의 7, 그 아래에 무늬 1의 7이 있다. 둘째 더미는 위에 무늬 2의 3, 그 아래에 무늬 2의 6이 있다. 이기는 방법 하나는 이렇다. 무늬 2의 3을 없애고, 무늬 2의 6을 없애면 둘째 더미가 빈다. 그 빈 더미로 무늬 2의 7을 옮기면 모든 더미에 카드가 한 장 이하만 남는다.

예제의 둘째 테스트 케이스에는 카드가 두 장씩인 더미가 셋 있다. 할 수 있는 이동은 무늬 4의 5를 없애는 것뿐이고, 그 뒤에 새로 열리는 이동은 없다.