A6086. 「BJOI2018」染色
编程题
NOI/NOI+/CTSC
知识点
题目描述
pupil 喜欢给图的顶点染颜色。有一天，master 想刁难他，于是给了他一个无重边和自环的无向图，
并且对每个点分别给了一个大小为 $2$ 的颜色集合，pupil 只能从这个集合中选一种颜色给这个点染色。master 希望 pupil 的染色方案使得没有两个有边相连的点被染了相同的颜色。
现在 pupil 想知道，是否无论 master 的颜色集合是什么，他均有办法按照要求染色。
并且对每个点分别给了一个大小为 $2$ 的颜色集合，pupil 只能从这个集合中选一种颜色给这个点染色。master 希望 pupil 的染色方案使得没有两个有边相连的点被染了相同的颜色。
现在 pupil 想知道，是否无论 master 的颜色集合是什么，他均有办法按照要求染色。
输入格式
输入包含多组数据。
第一行一个正整数 $T$，表示数据组数。
之后每组数据第一行两个空格隔开的整数 $n,m$，表示这个无向图的点数和边数。
之后 $m$ 行，每行两个空格隔开的正整数 $i,j$，表示图中的一条连接点 $i$ 和点 $j$ 的边。
图的节点从 $1$ 开始标号。
第一行一个正整数 $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
说明/提示
对于 $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$。
对于 $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$。