시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 (하단 참고) | 256 MB | 57 | 18 | 14 | 32.558% |
당신은 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"를 출력한다. (모두 대문자이며 따옴표는 제외)
3 3 3 1 2 2 3 3 1 4 4 1 2 2 3 3 4 4 1 6 6 1 2 2 3 1 4 1 5 6 2 4 6
NO YES YES
예제 1과 예제 2는 문제에서 다루었다.
예제 3의 경우 {1, 3, 6} 과 {2, 4, 5} 로 나눌 수 있다.