#P17836. [Ontak2022]TRE
[Ontak2022]TRE
题目描述
对于无向图 ,定义其线图 :
- 的每条边对应 中的一个顶点;
- 当且仅当两条不同的原图边具有公共端点时,对应的线图顶点相邻。
给定一个简单无向图 ,判断是否存在一棵树 ,使 与 同构;若存在,构造任意一棵这样的树。
输入格式
第一行一个整数 ,表示测试组数。
每组第一行两个整数 ,表示 的顶点数和边数。顶点编号为 。接下来 行,每行两个端点编号,表示一条边。保证 无自环、无重边。
输出格式
每组先输出一行 YES 或 NO。
如果存在,再输出一行树 的顶点数 。任选一种编号方式将其顶点编号为 ,随后输出 行树边端点。任意正确的树均可;原题未要求按输入 的顶点编号排列所输出的树边。
数据范围
;;;所有测试组的 之和不超过 。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 一定有解,且原树是一条路径或星形 | 15 |
| 2 | n≤100,且所有 n² 之和≤10000 | 55 |
| 3 | n≤7 | 7 |
| 4 | n≤500 | 11 |
| 5 | 无额外限制 | 12 |
样例 1
输入:
2
5 7
3 2
3 5
3 1
2 5
2 1
1 5
1 4
3 1
1 2
输出:
YES
6
1 2
1 3
3 4
3 5
3 6
NO