장난감 동맹군
면접 대비시간 제한1.5초메모리 제한256 MB
N개의 장난감과 M개의 서로 싫어하는 쌍이 주어질 때, 같은 편에 싫어하는 쌍이 없도록 두 편으로 나눌 수 있는지, 즉 그래프가 이분 그래프인지 판별한다.
문제
당신은 N개의 동물 장난감으로 모의 전쟁 놀이를 하려고 한다. 장난감에는 편의상 1부터 N까지 번호가 붙어 있고, 이 장난감들을 두 개의 동맹군으로 나누려고 한다. 다만 특정 장난감끼리는 사이가 나쁠 수 있는데(예를 들어 강아지 장난감과 고양이 장난감, 배트맨과 조커), 그러한 장난감 쌍은 같은 동맹군에 속할 수 없다.
예를 들어 N = 3이고 (1, 2), (2, 3), (3, 1)이 서로 동맹이 될 수 없다고 하자. 이 경우 세 장난감을 어떻게 두 동맹군으로 나누더라도 두 동맹군 중 하나는 동맹이 될 수 없는 관계인 장난감 쌍을 가지므로 나누는 것이 불가능하다. 다른 예로 N = 4이고 (1, 2), (2, 3), (3, 4), (4, 1) 네 쌍의 관계가 주어진다면 {1, 3}과 {2, 4} 두 동맹군으로 나눌 수 있다.
이렇게 여러 이유로 서로 동맹이 될 수 없는 장난감 쌍이 총 M개 주어졌을 때, N개의 장난감을 두 개의 동맹군으로 나누되 서로 동맹이 될 수 없는 장난감 쌍은 서로 다른 동맹군에 속하도록 나누려고 한다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 N과 M이 공백으로 구분되어 주어진다.
다음 M줄에 걸쳐 각 줄에 한 쌍의 장난감 번호가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 N개의 장난감을 두 동맹군으로 나눌 수 있으면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력한다. (모두 대문자이며 따옴표는 제외)
제한
- 1 ≤ T ≤ 10
- 각 줄에 주어지는 장난감 쌍의 번호가 같은 경우는 입력으로 주어지지 않는다
- 한 테스트 케이스 내에서 같은 장난감 한 쌍이 입력으로 여러 번 주어지지 않는다 (가령 x y가 한 번 입력으로 주어지면 x y 혹은 y x는 같은 테스트 케이스에서 다시 입력으로 주어지지 않는다)