在计算机科学中，栈 $s$ 是一种维护元素列表的数据结构，包含两种操作： $s.\text{push}(e)$ 将元素 $e$ 添加到列表的最右端。 $s.\text{pop}()$ 移除列表最右端的元素并返回该元素。

为方便起见，Bobo 用 $\text{size}(s)$ 表示栈 $s$ 中的元素个数，用 $\text{right}(s)$ 表示最右端的元素。

Bobo 有 $m$ 个栈 $s_1, \dots, s_m$。初始时，栈 $s_i$ 包含 $k_i$ 个元素 $a_{i,1}, \dots, a_{i,k_i}$，其中 $a_{i,j} \in \{1, \dots, n\}$。此外，对于每个 $e \in \{1, \dots, n\}$，元素 $e$ 在这 $m$ 个栈中恰好出现两次。因此，$k_1 + \dots + k_m = 2n$。

一个长度为 $l$ 的排序方案由 $l$ 个二元组 $(f_1, t_1), \dots, (f_l, t_l)$ 组成。执行排序方案时，对于每个 $i \in \{1, \dots, l\}$，按顺序执行 $s_{t_i}.\text{push}(s_{f_i}.\text{pop}())$。

如果排序方案的长度不超过 $\lfloor \frac{3n}{2} \rfloor$，且对于每个 $i \in \{1, \dots, l\}$，满足 $1 \le f_i, t_i \le m$ 且 $f_i \neq t_i$，则该方案是合法的。在第 $i$ 次操作前，必须满足： $\text{size}(s_{f_i}) > 0$ $\text{size}(s_{t_i}) < 2$ * $\text{size}(s_{t_i}) = 0$ 或 $\text{right}(s_{f_i}) = \text{right}(s_{t_i})$

此外，在执行完一个合法的排序方案后，每个栈要么为空，要么包含两个相同的元素。

给定 $m$ 个栈的初始配置，求出一个合法的排序方案。

输入格式

输入包含多个测试用例，以文件结束符（EOF）终止。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$。 接下来的 $m$ 行，第 $i$ 行包含一个整数 $k_i$，以及 $k_i$ 个整数 $a_{i,1}, \dots, a_{i,k_i}$。

• $1 \le n \le m \le 2 \times 10^5$
• 对于每个 $1 \le i \le m$，$0 \le k_i \le 2$
• 对于每个 $1 \le i \le m, 1 \le j \le k_i$，$1 \le a_{i,j} \le n$
• 对于每个 $1 \le e \le n$，恰好存在两个 $(i, j)$ 满足 $1 \le j \le k_i$ 且 $a_{i,j} = e$
• 在每个输入中，$m$ 的总和不超过 $2 \times 10^5$

输出格式

对于每个测试用例，如果存在合法的排序方案，输出一个整数 $l$，表示排序方案的长度。随后输出 $l$ 行，第 $i$ 行包含两个整数 $f_i$ 和 $t_i$。否则，输出 -1。

如果存在多个合法的排序方案，输出其中任意一个即可。

样例

输入 1

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

输出 1

3
1 3
2 3
2 1
0
-1

说明

对于第一个测试用例： 初始时，$s_1 = [1, 2], s_2 = [1, 2], s_3 = [ ]$。 执行 $s_3.\text{push}(s_1.\text{pop}())$ 后，$s_1 = [1], s_2 = [1, 2], s_3 = [2]$。 执行 $s_3.\text{push}(s_2.\text{pop}())$ 后，$s_1 = [1], s_2 = [1], s_3 = [2, 2]$。 执行 $s_1.\text{push}(s_2.\text{pop}())$ 后，$s_1 = [1, 1], s_2 = [ ], s_3 = [2, 2]$。

对于第二个测试用例，初始配置已经排好序。