P13854 [CERC 2023] Jumbled Stacks

我们有一组 $n$ 张卡片，标号从 $1$ 到 $n$，它们被分配到 $k$ 个牌堆中，记为 $S_1, S_2, \ldots, S_k$。每个牌堆都有容量限制：第 $i$ 个牌堆 $S_i$ 最多能容纳 $C_i$ 张卡片。我们唯一可以进行的操作是：从某个牌堆的顶部取出一张卡片，将其移动到 **另一个** 牌堆的顶部（前提是不会超过目标牌堆的容量）。 通过若干次这样的操作，我们希望将卡片重新排列，使得满足以下条件： 1. 从 $S_1$ 开始的若干个牌堆（可能是 $0$ 个或更多）被完全填满； 2. 紧接着的下一个牌堆未被填满（甚至可能为空）； 3. 后面的所有牌堆完全为空； 4. 如果我们把所有牌堆依次从 $S_1$ 在底部到 $S_k$ 在顶部依次堆叠起来，卡片应当从下到上严格升序排列，即 $1$ 在最底部，$n$ 在最顶部。 题目保证以下条件成立： $$ n \leq \left( \sum_{i=1}^{k} C_i \right) - \max_{1 \leq i \leq k} C_i $$ 例如，假设我们有 $n = 6$ 张卡片，$k = 3$ 个牌堆，且容量分别为 $C_1 = 4$, $C_2 = C_3 = 3$。初始状态如下（牌堆从底到顶给出，$0$ 表示该位置为空）： - $S_1 = [2, 3, 0, 0]$ - $S_2 = [4, 1, 6]$ - $S_3 = [5, 0, 0]$ 那么目标状态是： - $S_1 = [1, 2, 3, 4]$ - $S_2 = [5, 6, 0]$ - $S_3 = [0, 0, 0]$

第一行包含两个整数 $n$ 和 $k$，分别表示卡片的数量和牌堆的数量。 接下来的 $k$ 行描述初始状态：第 $i$ 行描述第 $i$ 个牌堆 $S_i$，包含 $C_i + 1$ 个整数： - 第一个整数为 $C_i$，表示牌堆容量； - 随后的 $C_i$ 个整数为牌堆中卡片的编号，从底部到顶部依次给出； - 如果该牌堆中的卡片数少于 $C_i$，则最后几个数用 $0$ 表示。

输出一系列操作，每行两个整数 $a, b$，表示将一张卡片从牌堆 $S_a$ 的顶部移动到牌堆 $S_b$ 的顶部（$1 \leq a, b \leq k$ 且 $a \neq b$）。 操作总数不能超过 $10^5$。 在所有操作结束后，输出一行：`0 0`。如果有多种可能的解法，可以输出任意一种。

### 注释 这是题面中给出的示例。上面的输出展示了 14 次移动操作，使牌堆达到期望状态。 ### 输入限制 - $1 \leq n \leq 100$ - $3 \leq k \leq 100$ - $1 \leq C_i \leq n$