#P18676. Classical Graph Theory Problem
Classical Graph Theory Problem
Classical Graph Theory Problem
给定一个连通的无向图 。
如果每个顶点 要么属于集合 ,要么至少有一个邻居属于 ,则称 为图的一个支配集。
一个顶点恰好有一个邻居时,称它为叶子。图满足:每个顶点的邻居中,至多有两个叶子。
请找出一个顶点集合 ,同时满足:
- 是图 的支配集;
- 也是图 的支配集;
- 。
保证满足要求的集合一定存在。
输入格式
每份输入包含多组测试。第一行是测试组数 ()。随后依次给出各组。
每组第一行是两个整数 ,分别表示顶点数和边数(,)。
接下来的 行,每行有两个整数 ,表示第 条边的两个端点(,)。图连通,没有自环或重边,每个顶点至多有两个叶子邻居。
保证所有测试组的 之和不超过 , 之和不超过 。
输出格式
对每组测试,输出 个互不相同的整数 ,表示集合 的顶点,顺序任意,编号均在 到 之间。
有多个合法答案时,输出其中任意一个。不需要输出集合大小。
样例输入 1
2
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
3 2
1 2
2 3
样例输出 1
2 3 6
2