#2493. 「BJOI2018」染色

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: qmqmqm

题目描述

pupil 喜欢给图的顶点染颜色。有一天,master 想刁难他,于是给了他一个无重边和自环的无向图, 并且对每个点分别给了一个大小为 2 的颜色集合,pupil 只能从这个集合中选一种颜色给这个点染色。master 希望 pupil 的染色方案使得没有两个有边相连的点被染了相同的颜色。

现在 pupil 想知道,是否无论 master 的颜色集合是什么,他均有办法按照要求染色。

输入格式

输入包含多组数据。

第一行一个正整数 T ,表示数据组数。

之后每组数据第一行两个空格隔开的整数 n,m ,表示这个无向图的点数和边数。

之后 m 行,每行两个空格隔开的正整数 i,j ,表示图中的一条连接点 i 和点 j 的边。

图的节点从 1 开始标号。

输出格式

对于每组数据,如果 pupil 无论如何均能染色,输出一行一个字符串 YES,否则输出一行一个字符串 NO

样例

样例输入

3
6 9
1 2
1 4
1 6
3 2
3 4
3 6
5 2
5 4
5 6
2 1
1 2
3 3
1 2
1 3
2 3

样例输出

NO
YES
NO

样例解释

对于第一组数据,如果第一个点和第二个点的集合为 \{A,B\} ,第三个点和第四个点的集合为 \{A,C\} ,第五个点和第六个点的集合为 \{B,C\} , 则奇数点至少使用了两种颜色,偶数点至少使用了两种颜色,因此至少有一个奇数点和一个偶数点颜色相同。但每两个奇数点和每两个偶数点之间均有边, 因此无法满足“没有两个有边相连的点被染了相同的颜色”。

对于第二组数据,无论两个集合是什么,第一个点随便染它的集合中的其中一种颜色,第二个点染它的集合中某个与第一个点不同的颜色即可。

对于第三组数据,如果三个点的集合均是 \{A,B\} ,那么无法满足“没有两个有边相连的点被染了相同的颜色”。

数据范围与提示

对于 10\% 的数据, 1 \leq n \leq 3

对于 20\% 的数据, 1 \leq n \leq 6

对于 50\% 的数据, 1 \leq n \leq 1000 0 \leq m \leq 2000

对于 100\% 的数据, 1 \leq n \leq 10000 0 \leq m \leq 20000 1 \leq T \leq 10