题目描述

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$ 的一行。

如果有多种可能的解决方案，只需打印其中任意一种。

3 3
1 2
2 1 3
0

3
2 3
1 3
2 3

7 3
4 1 2 5 7
1 4
2 3 6

-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\%$ 的分数。你不需要打印后续行即可获得这些分数。