P13183 [GCJ 2017 Finals] Stack Management

你正在玩一个单人纸牌游戏，桌面上有 $\mathbf{N}$ 堆明面朝上的牌，第 $i$ 堆起始时有 $\mathbf{C_i}$ 张牌。每张牌都有一个点数和值，以及一个花色，并且游戏中不存在两张点数与花色组合完全相同的牌。 每一步，你可以进行以下两种操作之一： 1. 如果有两张或更多花色相同的牌，且它们分别位于不同的牌堆顶端，你可以从这些牌中移除点数最小的那一张离开游戏。（当你移除某堆的最后一张牌时，该堆仍然存在，只是变为空堆。） 2. 如果有空堆，你可以从任意一个非空堆顶取一张牌，放到任意一个空堆上（即此时该空堆变为只含这一张牌）。 如果你能够通过一系列操作，最终使得每一堆牌最多只剩下一张牌，则你赢得了游戏。给定初始的牌堆排列，判断是否有可能赢得游戏。

输入的第一行包含一个整数 $\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$ 开始计数）。

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

**样例解释** 在样例第 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 完成。