#P18130. Unusual Case

Unusual Case

Unusual Case

给定一张随机无向图。这张图是从所有具有 nn 个顶点、mm 条边的无向简单图中独立、均匀随机选出的。

再给定整数 kk。请找出 kk 条互不重复使用边的 Hamiltonian 路径。

一条路径称为 Hamiltonian 路径,当且仅当它恰好经过图中的每个顶点一次。

本题有 1 个样例和恰好 30 个正式测试点。除样例外,所有测试点都满足

n=10000,m=200000,k=8.n=10000,\qquad m=200000,\qquad k=8.

输入格式

第一行包含三个整数 n,m,kn,m,k,分别表示顶点数、边数和需要构造的路径数。

接下来 mm 行,每行包含两个整数,表示一条无向边的两个端点,编号从 11 到 nn。图中没有自环,也没有重边。

输出格式

输出 kk 行。每行包含 nn 个整数,表示一条 Hamiltonian 路径依次经过的顶点。

任意一条边最多只能出现在一条输出的路径中。若有多组合法答案,输出任意一组。保证每个测试点均有解。

样例

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

一种合法输出为:

1 3 5 2 4
5 1 4 3 2

样例是唯一一个不满足正式测试点统一约束的测试。样例也是评测系统中的第 1 个测试点。