← 返回题目
题库练习 染色
← 上一题 下一题 →

A2708 | 染色

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

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

输入格式

输入包含多组数据。

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

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

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

图的节点从 $1$ 开始标号。

输出格式

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

输入输出样例

输入 #1
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
输出 #1
NO
YES
NO
C++ 编辑器
输入
输出