#P4878. [Lydsy1705月赛]挑战NP-Hard
[Lydsy1705月赛]挑战NP-Hard
题目描述
天才大学生 quailty 热衷于解决 NP-Hard 问题。给定一张无向图 和整数 ,你只需完成下面两项中的任意一项。
- 图染色。给每个点选一个 至 的整数作为颜色,使每条边两端的颜色不同。
- 简单 路径。找到一条恰好经过 条边的简单路径。也就是找到 个两两不同的点 ,使每对相邻的点 之间都有一条边。
输入格式
第一行一个正整数 ,表示数据组数,。
每组首先输入三个正整数 ,其中 和 分别为点数和边数,,,。
接下来 行,每行两个整数 ,表示连接点 的一条无向边,。保证无重边、无自环,所有组的边数之和不超过 。
输出格式
每组输出一行。若选择染色,先输出 color,再按点编号递增的顺序输出 个颜色。若选择输出路径,先输出 path,再按路径顺序输出 个点的编号。各项以空格分隔。若有多种合规输出,任选一种。
样例 #1
输入 #1
2
4 5 2
1 2
2 3
3 4
4 1
1 3
3 3 3
1 2
2 3
3 1
输出 #1
path 3 2 1
color 1 2 3
相关
在下列比赛中: