Description

我们有一组 $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]$

Input Format

第一行包含两个整数 $n$ 和 $k$，分别表示卡片的数量和牌堆的数量。

接下来的 $k$ 行描述初始状态：第 $i$ 行描述第 $i$ 个牌堆 $S_i$，包含 $C_i + 1$ 个整数：

• 第一个整数为 $C_i$，表示牌堆容量；
• 随后的 $C_i$ 个整数为牌堆中卡片的编号，从底部到顶部依次给出；
• 如果该牌堆中的卡片数少于 $C_i$，则最后几个数用 $0$ 表示。

Output Format

输出一系列操作，每行两个整数 $a, b$，表示将一张卡片从牌堆 $S_a$ 的顶部移动到牌堆 $S_b$ 的顶部（$1 \leq a, b \leq k$ 且 $a \neq b$）。
操作总数不能超过 $10^5$。

在所有操作结束后，输出一行：0 0。如果有多种可能的解法，可以输出任意一种。

6 3
4 2 3 0 0
3 4 1 6
3 5 0 0

2 3
2 3
1 2
1 2
3 1
2 1
2 1
3 2
3 1
2 3
1 3
2 1
3 2
3 2
0 0

Hint

注释

这是题面中给出的示例。上面的输出展示了 14 次移动操作，使牌堆达到期望状态。

输入限制

• $1 \leq n \leq 100$
• $3 \leq k \leq 100$
• $1 \leq C_i \leq n$