Sir Hamilton 热衷于长途跋涉……

给定一个包含 $n$ 个顶点和 $m$ 条边的随机无向图：该图是从所有具有相同顶点数和边数的图中随机且均匀选取的。同时给定一个整数 $k$。你的任务是在给定的图中找到 $k$ 条不相交的哈密顿路径。

如果一条路径恰好经过图中所有顶点一次，则称其为哈密顿路径。

在本题中，包含一个样例和 30 个测试点。除样例外，所有测试点均满足 $n = 10\,000$，$m = 200\,000$，$k = 8$。

输入格式

第一行包含三个整数：顶点数 $n$，边数 $m$，以及需要找到的路径数 $k$。

接下来 $m$ 行包含图的边描述。每条边由一对 $1$ 到 $n$ 之间的整数描述，表示该边连接的两个顶点。图中没有自环和重边。

输出格式

输出 $k$ 行。每行输出一条哈密顿路径：即遍历顺序下的 $n$ 个顶点序列。图中每条边在输出的路径中最多只能被使用一次。如果存在多种可能的答案，输出其中任意一个即可。保证对于给定的每个测试点，答案一定存在。

样例

样例输入 1

5 9 2
1 3
1 4
1 5
2 3
2 4
2 5
3 5
4 3
5 4

样例输出 1

1 3 5 2 4
5 1 4 3 2

说明

题目中的样例是唯一一个不满足 $n = 10\,000$，$m = 200\,000$，$k = 8$ 的测试点。它仅用于演示输入和输出格式。该样例在测试系统中为测试点 1。