U169194 【模板】二分图判定

对于无向图 $G=(V,E)$，如果可以把结点集分成不相交的部分，即 $X$ 和 $ Y=V-X$，使得每条边的其中一个端点在 $X$ 中，另一个在 $Y$ 中，则称 $ G $ 为二分图（bipartite graph）。 二分图的另一种等价说法是，可以把每个结点着以黑色和白色之一，使得每条边的两个端点颜色不同，所以**黑白染色法**这就是判定二分图的基本算法。 不难发现，非连通图是二分图当且仅当每个连通分量都是二分图。比如下面的问题就是典型的二分图判定问题：

期末考试的时候，老师要把全班学生分在两个考场。 老师在分考场的时候要考虑尽量避免把相互之间比较熟悉的同学分在同一的考场，因为他们可能会联合起来作弊。 现在老师统计了同学们相互之间熟悉情况，他想知道能否合理地分考场，将所有相互熟悉的同学分在不同的考场

输入第一行是一个整数 $T$，表示有 $T（T\leq20）$ 组测试数据。 接下来每一组测试数据包括两个部分。 第一部分只有一行，有两个整数 $n$,$m$$（2 \leq n\leq 1000 ,m \leq \dfrac{n(n-1)}{2}）$, 分别表示学生的人数和老师掌握的学生之间熟悉关系个数。 第二部分有 $m$ 行，每行有两个整数 $a$,$b$，表示学生 $a$ 和学生 $b$ 相互认识，即有可能联合起来作弊。$a$ 和 $b$ 分别表示学生的标号，且从 $1$ 开始 $（1 \leq a,b \leq n）$

对于每组测试数据，输出按照样例的格式。 第一行表示是第几组数据，即输出 “case n:”。 如果能把所有学生分在两个考场，且不可能发生作弊行为，则第二行输出 Yes，否则输出 No。

$T \leq 20 \leq n \leq 1000,m \leq \dfrac{n(n-1)}{2}$ $ update (2023.8.21) $ : 当时不会用Markdown的数学，导致题面不太好看。现在会写博客了，顺便来改改。当时是上课随便弄的，没想到这么多人提交，本蒟蒻属实受宠若惊了哈哈