[BOJ] 1707. 이분 그래프

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int check[];
	static List<Integer> list[];
	static int T,V,E;
	static boolean bisectFlag;
	static boolean connectFlag;
	public static void main(String[] args) {
		T=sc.nextInt();
		for (int t = 0; t < T; t++) {
			init();
			for (int i = 1; i <= V; i++) {
				if(check[i]==0) {
					dfs(i,1);		
				}
			}
			if(bisectFlag) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}
		
	}
	
	public static void dfs(int v,int d) {
		check[v]=d;
		for (int i = 0; i < list[v].size(); i++) {
			int nv=list[v].get(i);
			if(check[nv]==0) {
				dfs(nv,d+1); 
			}else {
				if(((check[v]+1)&1)!=(check[nv]&1)) { bisectFlag=false; return;}
			}
		}
	}
	
	public static void init() {
		bisectFlag=true;
		connectFlag=true;
		V=sc.nextInt();
		E=sc.nextInt();
		check=new int [V+1];
		list=new List[V+1];
		
		for (int i = 1; i <= V; i++) {
			list[i]=new ArrayList<Integer>();
		}		
		
		for (int i = 0; i < E; i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			list[a].add(b);
			list[b].add(a);
		}
	}
}