问题1215--图中修边

1215: 图中修边

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述


给定一个n(\(1\le n\le 100000\))个点m(\(1\le m\le 500000\))个边的简单无向图,

可以进行有限次如下的操作:
1.  选择三个点a,b,c
2.  操作之前,a和b之间不存在边,a和c、b和c之间都需要存在边。
3.  操作之后,a和b之间新增一条边,ac,bc之间的两条边消失

问,给定的图是否可以在有限次操作之后,令图中所有点的度数小于等于1



输入

第一行是一个整数t,代表数据组数
第二行两个整数n和m,如题面描述
接下来m行,每行两个整数,代表这两个点之间有一条边
保证是简单图(没有自环和重边)

输出

如果存在解法,输出"YES"
否则输出"NO"

样例输入 Copy

1
3 2
1 2 
2 3

样例输出 Copy

YES

提示

样例进行(2,1,3)操作,12和23边消失,13边出现,然后所有点度数小于等于1


其实本题可以线性输出方案,难度大概是出线难度,校内外的神仙可以想想这个做法。




\( \sum{n}<=1e5 \\ \sum{m}<5e5 \)