在 NERC 2020 在线赛中没有关于仙人掌图的题目。这是一个严重的失误，所以评委们决定修复它。如果不解决一道关于仙人掌图的题目，你就无法进入 2021 年世界总决赛！

仙人掌图是一个连通的无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是树的一种推广，允许存在一些环。仙人掌图中不允许存在多重边（一对顶点之间有多条边）和自环（连接顶点自身的边）。

Cher 有一个仙人掌图。如果无法在不破坏其仙人掌图性质的前提下添加任何边，她称该仙人掌图为“强”仙人掌图。但 Cher 认为她的仙人掌图不够强。她想在图中添加最少数量的边，使其变为强仙人掌图，即创建一个具有相同顶点集的新仙人掌图，使得原仙人掌图是新图的子图，且无法再添加任何边而不破坏仙人掌图的性质。Cher 雇佣你来完成这项工作。所以……这就要靠你了！

输入格式

输入包含一个或多个独立的测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$, $0 \le m \le 10^5$)，其中 $n$ 是图中的顶点数。顶点编号从 $1$ 到 $n$。图的边由一组边不相交的路径表示，其中 $m$ 是这些路径的数量。

接下来的 $m$ 行，每行包含图中的一条路径。路径以一个整数 $s_i$ ($2 \le s_i \le 1000$) 开头，后跟 $s_i$ 个 $1$ 到 $n$ 之间的整数。这些 $s_i$ 个整数表示路径上的顶点。

路径中相邻的顶点是不同的。路径可以多次经过同一个顶点，但整个测试用例中每条边恰好被遍历一次。图中不存在多重边（任意两个顶点之间最多只有一条边）。

输入在所有测试用例之后以两个零结尾。这不定义测试用例，仅标记输入的结束，不需要输出。

输入中的所有图均为仙人掌图。整个输入中 $n$ 的总和与 $m$ 的总和均不超过 $10^5$。

输出格式

对于每个测试用例，首先输出一行，包含需要添加的最少边数 $A$。然后输出 $A$ 行，每行描述一条边 $u_i \ v_i$，其中 $u_i$ 和 $v_i$ 是要连接的顶点编号。添加这些边后，所得图必须是一个强仙人掌图。

样例

样例输入 1

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

样例输出 1

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