[백준,PS,그래프탐색][PYTHON] #1707. 이분그래프

from collections import deque


def bfs(x):
    global stop
    q.append(x) #초기작업 : 큐에넣고
    visited[x] = 1#방문표시하고
    level[x] = 1   #레벨1이라고 명시
    while q:
        x = q.popleft()
        
        for i in range(len(a[x])):
            nx = a[x][i]
            if (visited[nx] ==0):#방문안한곳이라면 
                visited[nx] = 1 #방문하고
                level[nx] = level[x] +1#레벨을 1증가시켜준다.
                q.append(nx)#그후에 인접한 노드들을 큐에 집어넣는다.
                
            if(visited[nx] ==1): #pop을 한후에 인접 노드들중 방문했던곳인데
                if (level[x] == level[nx]): # 나와 레벨이 같은 노드가 있다면 이분그래프가 될수 없는 것이다.
                    stop +=1
                    return -1

test_case = int(input())

for i in range(test_case):
    vertex , edge = map(int, input().split())
    a =[ [] for _ in range(vertex+1)]
    visited =[ 0 for _ in range(vertex+1)]
    level = [ 0 for _ in range(vertex+1)]
    q = deque()
    stop = 0
    
    for _ in range(edge):
        x,y = map(int, input().split())
        a[x].append(y)
        a[y].append(x)
  
    bfs(1)
    
    for i in range(len(visited)): #만약 방문하지 않은 곳이 있다면(즉 , 끊긴 그래프 이기때문에 BFS를 수행하지 못한곳이 있는지 확인하기위한 작업)
        if visited[i] ==0:
            bfs(i)#BFS 추가실시
    
    if (stop>=1 ): #stop 플래그에 따른 대답
        print("NO")
    else:
        print("YES")