5640번 - 즐거운 색칠 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 71 | 29 | 14 | 41.176% |
문제
즐거운 색칠 문제는 다음과 같다.
유한 집합 \(U\)와 \(\left| S_i \right| \le 3\)를 만족하는 집합 \(S_1,S_2,S_3,\dots ,S_m \subseteq U \) 가 있다.
문제: 적어도 \(S_i\)의 한 원소가 다른 원소의 색과 다르게 할당하는 함수 \(f:U\mapsto \left\{ RED,BLUE \right\} \) 가 존재하는가?
즐거운 색칠 문제가 주어졌을 때, 그러한 함수 \(f\)가 존재하는지 알아내는 프로그램을 작성하시오.
입력
이 문제에서 \(U =\left\{ x_1,x_2,\dots , x_n \right\} \) 이다.
첫째 줄에는 테스트 케이스의 개수 $k$가 주어진다. 각 테스트 케이스는 빈 줄로 구분된다.
테스트 케이스의 첫째 줄에는 $n$과 $m$이 주어진다. 다음 $m$개 줄의 $i$번째 줄에는 \(S_i\)에 포함되는 \(x_i\)의 $i$가 공백으로 구분해서 주어진다.
출력
각 테스트 케이스마다 함수 \(f\)가 존재하면 'Y', 아니면 'N'을 출력한다. 모든 정답은 한 줄에 붙여서 순서대로 출력한다.
제한
- $1 ≤ k ≤ 13$
- $4 ≤ n ≤ 22$
- $3 ≤ m ≤ 111$
예제 입력 1
2 5 3 1 2 3 2 3 4 1 3 5 7 7 1 2 1 3 4 2 4 3 2 3 1 4 5 6 7
예제 출력 1
YN
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호