#P2493. 「BJOI2018」染色

「BJOI2018」染色

题目描述

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

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

输入格式

输入包含多组数据。

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

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

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

图的节点从 11 开始标号。

输出格式

对于每组数据,如果 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

数据范围与提示

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

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

对于 50%50\% 的数据,1n10001 \leq n \leq 10000m20000 \leq m \leq 2000

对于 100%100\% 的数据,1n100001 \leq n \leq 100000m200000 \leq m \leq 200001T101 \leq T \leq 10