一天fly正坐在课堂上发呆，突然，他注意到了桌面上的一个字符串S1S2S3S4...Sn，这个字符串只由字符"a"，"b"和"c"构成。刚好这堂课很无聊，所以他决定为这个字符串画一张图，（这张图上的每个点代表字符串中的一个字符，例如节点1代表S1。）这张图有以下特点：
fly根据这个字符串画出了图，随后把原先的字符串擦除了，于是桌面只留下了图。xf听说了fly的光荣事迹，第二天决定去一睹真迹，于是他来到了fly那天所在的教室的那张桌子前，然而眼前的一幕让他惊呆了：桌子上出现了好多幅图，显然这是某个别有用心的同学（GooZy?）私自画上去的。这可急坏了xf，于是他想请你帮他找出哪幅才是fly真迹。
输入
输入包含多组数据。第一行为一个整数T(1 ≤ T ≤ 100)，代表数据组数，对于每组数据： 第一行是两个整数n和m( 1 ≤ n ≤ 500, 0 ≤ m ≤ n(n − 1)/2 )，分别代表图上点的个数和边的个数。
然后是m行，每行两个整数u和v ( 1 ≤ u, v ≤ n, u ≠ v )，代表图上的一条边所连接的两个点。输入保证没有重边。
输出
如果是fly真迹，即这张图是由题目描述中的字符串构成的，则输出“Yes”，否则输出“No”(不包含双引号)。
样例输入
3
2 1
1 2
4 3
1 2
1 3
1 4
4 4
1 2
1 3
1 4
2 3
样例输出
Yes
No
Yes
HINT
对于样例1，fly见到的字符串可能长这个样子：aa, bb, cc...
对于样例2，结点1和其它所有的点相连，但是结点2、3、4互不相连，这说明这三者互不相邻，而我们只有三个字符，不可能存在这样的字符串满足这张图，所以这幅图不是fly的真迹。
对于样例3，我们可以构造这样的字符串“baac”来满足这张图。
------------------------------------------------------我是分割线^_^------------------------------------------------------------
题目大意：一个点可能为a、b、c三个值，字典序相邻的点之间必须有一条边，给出一些点组成的图，判定这个图是否合法。
解题思路：从反面考虑，没有连边的点对，一定是一个为a、一个为c，所以问题就转化成了二分图判定。但是要注意，染色
之后，颜色相同的点之间必须有边，颜色不同的点之间不能有边。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std; #define Int __int64
#define INF 0x3f3f3f3f const int MAXN = 555;
int maze[MAXN][MAXN];
int color[MAXN];
bool ans; void BFS(int t, int n) {
queue<int>q;
while (!q.empty()) q.pop();
color[t] = 1;
bool app = true;//用来确定是否还原标记= =，就是少了这一点
q.push(t);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (now == i) continue;
if (!maze[now][i] && color[i] == -1) {
app = false;
q.push(i);
color[i] = !color[now];
}
if (!maze[now][i] && color[now] == color[i]) {
ans = false;
return ;
}
}
}
if (app) color[t] = -1;
} int main()
{
//freopen("input.txt", "r", stdin);
int cas;
while (scanf("%d", &cas) != EOF) {
while (cas--) {
memset(maze, 0, sizeof(maze));
memset(color, -1, sizeof(color));
int n, m;
scanf("%d %d", &n, &m);
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
maze[u][v] = maze[v][u] = 1;
}
ans = true;
for (int i = 1; i <= n; i++) {
//判断负一，如果该点没有被染色，就开始对其进行染色= =
if (color[i] == -1) {
BFS(i, n);
}
}
for (int i = 1; i <= n; i++) {
if (!ans) break;
for (int j = 1; j <= n; j++) {
if (i == j || color[i] == -1 || color[j] == -1) continue;//判断条件
if (maze[i][j] && color[i] != color[j]) {
ans = false;
break;
}
if (!maze[i][j] && color[i] == color[j]) {
ans = false;
break;
}
}
}
if (ans) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}