P4429 [BJOI2018] 染色

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

无

无

### 样例解释 对于第一组数据，如果第一个点和第二个点的集合为 $\{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$。 - 另外存在 5 个不计分的 hack 数据。