一天fly正坐在课堂上发呆，突然，他注意到了桌面上的一个字符串S1S2S3S4...Sn，这个字符串只由字符"a"，"b"和"c"构成。刚好这堂课很无聊，所以他决定为这个字符串画一张图，（这张图上的每个点代表字符串中的一个字符，例如节点1代表S1。）这张图有以下特点：

1.它有n个点，从1到n进行标号。

2.对于图上任意的两个点i和j(i ≠ j)，当两者代表的字符在字典序顺序上相邻或者相等的时候，会被连上一条边。也就是说，"a"-"b", "a"-"a"这类的，它们间会有一条边相连，而"a"-"c"这类的就没有边相连。

fly根据这个字符串画出了图，随后把原先的字符串擦除了，于是桌面只留下了图。xf听说了fly的光荣事迹，第二天决定去一睹真迹，于是他来到了fly那天所在的教室的那张桌子前，然而眼前的一幕让他惊呆了：桌子上出现了好多幅图，显然这是某个别有用心的同学（GooZy?）私自画上去的。这可急坏了xf，于是他想请你帮他找出哪幅才是fly真迹。

输入

输入包含多组数据。第一行为一个整数T(1 ≤ T ≤ 100)，代表数据组数，对于每组数据： 第一行是两个整数n和m( 1 ≤ n ≤ 500, 0 ≤ m ≤ n(n − 1)/2 )，分别代表图上点的个数和边的个数。

然后是m行，每行两个整数u_i和v_i ( 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i )，代表图上的一条边所连接的两个点。输入保证没有重边。

输出

如果是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
    
     #include
     
      #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              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
             
              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