시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 19 9 9 52.941%

문제

즐거운 색칠 문제는 다음과 같다.

유한 집합 \(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가 공백으로 구분되서 주어진다.

1 ≤ k ≤ 13, 4 ≤ n ≤ 22, 6 ≤ m ≤ 111

출력

각 테스트 케이스마다 함수 \(f\)가 존재하면 'Y'를, 아니면 'N'을 출력한다. 모든 정답은 한 줄에 붙여서 순서대로 출력한다.

예제 입력

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

예제 출력

YN

힌트