19240번 - 장난감 동맹군 서브태스크다국어분류
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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"를 출력한다. (모두 대문자이며 따옴표는 제외)
제한
- 1 ≤ T ≤ 10
- 각 줄에 주어지는 장난감 쌍의 번호가 같은 경우는 입력으로 주어지지 않는다
- 한 테스트 케이스 내에서 같은 장난감 한 쌍이 입력으로 여러 번 주어지지 않는다 (가령 x y 가 한 번 입력으로 주어지면 x y 혹은 y x 는 같은 테스트 케이스에서 다시 입력으로 주어지지 않는다)
서브태스크 1 (4점)
- 1 ≤ T ≤ 10
- 3 ≤ N ≤ 16
- 1 ≤ M ≤ 16
서브태스크 2 (8점)
- 1 ≤ T ≤ 10
- 3 ≤ N ≤ 300,000
- 1 ≤ M ≤ 300,000
예제 입력 1
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
예제 출력 1
NO YES YES
예제 1과 예제 2는 문제에서 다루었다.
예제 3의 경우 {1, 3, 6} 과 {2, 4, 5} 로 나눌 수 있다.
시간 제한
- Java 8: 4 초
- Python 3: 6 초
- PyPy3: 6 초
- Java 8 (OpenJDK): 4 초
- Java 11: 4 초
- Python 2: 6 초
- PyPy2: 6 초
- Kotlin (JVM): 4 초
- Java 15: 4 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2021 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호