#P17836. [Ontak2022]TRE

[Ontak2022]TRE

题目描述

对于无向图 G=(V,E)G=(V,E),定义其线图 L(G)L(G):

  • GG 的每条边对应 L(G)L(G) 中的一个顶点;
  • 当且仅当两条不同的原图边具有公共端点时,对应的线图顶点相邻。

给定一个简单无向图 HH,判断是否存在一棵树 TT,使 L(T)L(T) 与 HH 同构;若存在,构造任意一棵这样的树。

输入格式

第一行一个整数 tt,表示测试组数。

每组第一行两个整数 n,mn,m,表示 HH 的顶点数和边数。顶点编号为 1,…,n1,\ldots,n。接下来 mm 行,每行两个端点编号,表示一条边。保证 HH 无自环、无重边。

输出格式

每组先输出一行 YES 或 NO。

如果存在,再输出一行树 TT 的顶点数 vv。任选一种编号方式将其顶点编号为 1,…,v1,\ldots,v,随后输出 v−1v-1 行树边端点。任意正确的树均可;原题未要求按输入 HH 的顶点编号排列所输出的树边。

数据范围

1≤t≤100001\le t\le10000;1≤n≤10001\le n\le1000;0≤m≤n(n−1)/20\le m\le n(n-1)/2;所有测试组的 n2n^2 之和不超过 10610^6。

子任务

子任务 附加限制 分值
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