BOJ 1707

package boj;

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

/**
 * Created by mkhwang on 2021/04/20
 * Email : orange2652@gmail.com
 * Github : https://github.com/myeongkwonhwang
 */
public class Boj1707 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        while(size-- > 0) {
            int vertex = sc.nextInt();
            int edge = sc.nextInt();

            ArrayList<Integer>[] adjacencyList = new ArrayList[vertex + 1];

            for (int j = 1; j <= vertex; j++) {
                adjacencyList[j] = new ArrayList<>();
            }

            for (int j = 0; j < edge; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();

                adjacencyList[x].add(y);
                adjacencyList[y].add(x);
            }
            int [] visited = new int[vertex+1];
            boolean result = true;
            for (int j = 1; j <= vertex; j++){
                if(visited[j] == 0){
                    if(dfs(adjacencyList, visited, j, 1) == false){
                        result = false;
                    }
                }
            }

            if(result) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static boolean dfs(ArrayList<Integer>[] adjacencyList, int[] visited, int vertex, int switchFlag) {
        visited[vertex] = switchFlag;
        for (int y : adjacencyList[vertex]) {
            if(visited[y] == 0){
                if(dfs(adjacencyList, visited, y, 3-switchFlag) == false){
                    return false;
                }
            }else if (visited[y] == visited[vertex]){ //직전의 flag와 동일하다면 false
                return false;
            }
        }
        return true;
    }

}