#P4878. [Lydsy1705月赛]挑战NP-Hard

    ID: 3990 传统题 1000ms 256MiB 尝试: 613 已通过: 181 难度: 5 上传者: 标签>难度分类普及+/提高-枚举与搜索深度优先搜索图论顶点着色路径恢复CF1800本OJ付费获得

[Lydsy1705月赛]挑战NP-Hard

题目描述

天才大学生 quailty 热衷于解决 NP-Hard 问题。给定一张无向图 GG 和整数 kk,你只需完成下面两项中的任意一项。

  • 图染色。给每个点选一个 11 至 kk 的整数作为颜色,使每条边两端的颜色不同。
  • 简单 kk 路径。找到一条恰好经过 kk 条边的简单路径。也就是找到 k+1k+1 个两两不同的点 v1,v2,…,vk+1v_1,v_2,\ldots,v_{k+1},使每对相邻的点 vi,vi+1v_i,v_{i+1} 之间都有一条边。

输入格式

第一行一个正整数 TT,表示数据组数,1≤T≤10001\leq T\leq 1000。

每组首先输入三个正整数 n,m,kn,m,k,其中 nn 和 mm 分别为点数和边数,1≤n≤10001\leq n\leq 1000,1≤m≤100001\leq m\leq 10000,1≤k≤n1\leq k\leq n。

接下来 mm 行,每行两个整数 a,ba,b,表示连接点 a,ba,b 的一条无向边,1≤a,b≤n1\leq a,b\leq n。保证无重边、无自环,所有组的边数之和不超过 10510^5。

输出格式

每组输出一行。若选择染色,先输出 color,再按点编号递增的顺序输出 nn 个颜色。若选择输出路径,先输出 path,再按路径顺序输出 k+1k+1 个点的编号。各项以空格分隔。若有多种合规输出,任选一种。

样例 #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