P14646 [POI 2025/2026 #1] 并非哈诺塔 / Hanoj

Bajtyna 最近在一个可疑的网站上买了一个玩具。她没有收到著名的汉诺塔谜题，而是在邮箱里发现了 Hanoj 塔。 Hanoj 塔由 $m$ 个堆组成，上面分布着 $n$ 个两两不同的积木，编号为从 $1$ 到 $n$ 的整数。在游戏开始时以及游戏的任何时刻，每个堆上的积木编号必须按照从堆顶到堆底递增的顺序排列。 在一步移动中，玩家可以从任意堆取走顶部的积木，并将其放置在任意堆的底部。 Bajtyna 现在想知道，要将所有积木放置在同一个堆上，最少需要多少步移动。帮她解决这个谜题。

输入的第一行包含两个整数 $n$ 和 $m$ （ $2 \le n \le 10^6$ ），分别表示积木的数量和堆的数量。堆用从 $1$ 到 $m$ 的整数编号。 接下来的 $m$ 行包含堆的描述。 第 $i$ 个堆（对于 $1 \le i \le m$）的描述由数字 $k_i,v_{i,1},v_{i,2}, ..., v_{i,k_i}$（ $0 \le k_i \le n$）组成，其中 $k_i$ 是第 $i$ 个堆上的积木数量，而 $v_{i,1}, ..., v_{i,k_i}$ 是这些积木的编号，按从堆顶到堆底的顺序给出。 所有给出的积木具有范围从 $1$ 到 $n$ 的两两不同的编号，每个这样的积木都位于某个堆上（即 $k_1 + \dots + k_m = n$ ）。

输出的第一行应打印一个整数 $h$，表示解决谜题所需的最少移动次数。接下来的 $h$ 行应包含后续移动的描述。 第 $i$ 步移动（对于 $1 \le i \le h$ ）的描述应由两个整数 $a_i,b_i$ （ $1 \le a_i, b_i \le m$ ）组成，表示将堆 $a_i$ 的顶部元素移动到堆 $b_i$ 的底部。 如果无法解决谜题，则应只打印包含 $-1$ 的一行。 如果有多种可能的解决方案，只需打印其中任意一种。

### 样例解释 - 样例 $1$ 中，首先我们将积木 1 从第二个堆的顶部移动到空的第三个堆。接下来，我们将积木 2 从第一个堆移动到第三个堆的底部。最后，我们将积木 3 从第二个堆移动到第三个堆的底部。这样，在游戏的任何时刻，每个堆上的积木编号都是递增排序的，并且在三次移动后，所有积木都位于第三个堆上。 - 样例 $2$ 中，解决谜题是不可能的。 ### 大样例 可以在附件中获得大样例。 样例 $\texttt{0a}$ 和 $\texttt{0b}$ 是题面中展示的样例。此外： - $\texttt{0c}$：10 个积木和两个堆，其中一个是空的。 - $\texttt{0d}$：1000 个积木和三个堆，其中一个是空的，其余两个分别包含编号为偶数和奇数的积木。 - $\texttt{0e}$：$10^6$ 个堆和 $10^6$ 个积木，每个堆上有一个。 ### 子任务 本题采用捆绑测试。 | 子任务编号 | 限制 | 得分 | | :---------: | :--------------------- | :-----: | | $1$ | $n \le 6$ | $15$ | | $2$ | $k_i = 0$ 对于某些 $i \in \{1, \dots, m\}$ | $27$ | | $3$ | $n \le 1000$ | $22 $ | | $4$ | $m = 3$ | $18 $ | | $5$ | 无额外限制 | $18$ | 如果你的答案只有第一行是正确的，你的解决方案将获得该测试 $50\%$ 的分数。你不需要打印后续行即可获得这些分数。