#P18130. Unusual Case
Unusual Case
Unusual Case
给定一张随机无向图。这张图是从所有具有 个顶点、 条边的无向简单图中独立、均匀随机选出的。
再给定整数 。请找出 条互不重复使用边的 Hamiltonian 路径。
一条路径称为 Hamiltonian 路径,当且仅当它恰好经过图中的每个顶点一次。
本题有 1 个样例和恰好 30 个正式测试点。除样例外,所有测试点都满足
输入格式
第一行包含三个整数 ,分别表示顶点数、边数和需要构造的路径数。
接下来 行,每行包含两个整数,表示一条无向边的两个端点,编号从 到 。图中没有自环,也没有重边。
输出格式
输出 行。每行包含 个整数,表示一条 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 个测试点。