Description

你正在玩一个单人纸牌游戏，桌面上有 $\mathbf{N}$ 堆明面朝上的牌，第 $i$ 堆起始时有 $\mathbf{C_i}$ 张牌。每张牌都有一个点数和值，以及一个花色，并且游戏中不存在两张点数与花色组合完全相同的牌。

每一步，你可以进行以下两种操作之一：

1. 如果有两张或更多花色相同的牌，且它们分别位于不同的牌堆顶端，你可以从这些牌中移除点数最小的那一张离开游戏。（当你移除某堆的最后一张牌时，该堆仍然存在，只是变为空堆。）
2. 如果有空堆，你可以从任意一个非空堆顶取一张牌，放到任意一个空堆上（即此时该空堆变为只含这一张牌）。

如果你能够通过一系列操作，最终使得每一堆牌最多只剩下一张牌，则你赢得了游戏。给定初始的牌堆排列，判断是否有可能赢得游戏。

Input Format

输入的第一行包含一个整数 $\mathbf{P}$，表示起始牌堆的数量。接下来有 $\mathbf{P}$ 行，每行描述一个起始牌堆。第 $i$ 行以一个整数 $\mathbf{C}_i$ 开头，表示第 $i$ 个起始牌堆中的牌数，随后是 $\mathbf{C}_i$ 个有序整数对。第 $j$ 个有序对为两个整数 $\mathbf{V}_{ij}$ 和 $\mathbf{S}_{ij}$，分别表示该堆自顶向下第 $j$ 张牌的点数和值与花色。

接下来一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为两个整数 $\mathbf{N}$ 和 $\mathbf{C}$，分别表示牌堆数量和每堆的牌数。随后一行有 $\mathbf{N}$ 个整数 $\mathbf{P}_i$，表示该测试用例所选用的起始牌堆编号（从 $0$ 开始计数）。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 为 POSSIBLE 表示可以赢得游戏，或 IMPOSSIBLE 表示不可能赢得游戏。

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

Hint

样例解释

在样例第 1 组中，有两堆，每堆两张牌。第一堆顶端是点数为 $7$、花色为 $2$ 的牌，下方是点数为 $7$、花色为 $1$ 的牌。第二堆顶端是点数为 $3$、花色为 $2$ 的牌，下方是点数为 $6$、花色为 $2$ 的牌。

可以按如下方式赢得游戏：

• 移除第二堆顶端的 $3$（花色 $2$）。
• 移除第二堆顶端的 $6$（花色 $2$）。此时第二堆为空。
• 将第一堆顶端的 $7$（花色 $2$）移动到第二堆。此时每堆最多只剩一张牌，达到胜利条件。

在样例第 2 组中，有三堆，每堆两张牌。在这种情况下无法赢得游戏；唯一的可行操作是移除第三堆顶端的 $5$（花色 $4$），但这并不会带来新的可行操作。

限制条件

• $1 \leq T \leq 100$。
• $2 \leq P \leq 60000$。
• 对所有 $i$，$0 \leq P_i < P$。
• 第 $P_i$ 个起始牌堆恰好有 $C$ 张牌。
• 每个测试用例中不存在两张牌点数与花色组合完全相同的情况。

小数据集（10 分，测试集 1 - 可见）

• $2 \leq N \leq 4$。
• 对所有 $i$，$2 \leq C_i \leq 13$。
• $2 \leq C \leq 13$。
• 对所有 $i, j$，$1 \leq V_{ij} \leq 13$。
• 对所有 $i, j$，$1 \leq S_{ij} \leq 4$。

大数据集（30 分，测试集 2 - 隐藏）

• $2 \leq N \leq 50000$。
• 对所有 $i$，$2 \leq C_i \leq 50000$。
• $2 \leq C \leq 50000$。
• $4 \leq N \times C \leq 10^5$。
• 对所有 $i, j$，$1 \leq V_{ij} \leq 50000$。
• 对所有 $i, j$，$1 \leq S_{ij} \leq 50000$。

翻译由 GPT4.1 完成。