시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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'을 출력한다. 모든 정답은 한 줄에 붙여서 순서대로 출력한다.

예제 입력 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
W3sicHJvYmxlbV9pZCI6IjU2NDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5OTBcdWFjNzBcdWM2YjQgXHVjMGM5XHVjZTYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5OTBcdWFjNzBcdWM2YjQgXHVjMGM5XHVjZTYwIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWQ1NWMgXHVjOWQxXHVkNTY5IFxcKFVcXClcdWM2NDAgXFwoXFxsZWZ0fCBTX2kgXFxyaWdodHwgJm5ic3A7IFxcbGUgM1xcKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjOWQxXHVkNTY5IFxcKFNfMSxTXzIsU18zLFxcZG90cyAsU19tIFxcc3Vic2V0ZXEgVSBcXCkgXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjOiBcdWM4MDFcdWM1YjRcdWIzYzQgXFwoU19pXFwpXHVjNzU4IFx1ZDU1YyBcdWM2ZDBcdWMxOGNcdWFjMDAgXHViMmU0XHViOTc4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWMwYzlcdWFjZmMgXHViMmU0XHViOTc0XHVhYzhjIFx1ZDU2MFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1NjhcdWMyMTggXFwoZjpVXFxtYXBzdG8gXFxsZWZ0XFx7IFJFRCxCTFVFIFxccmlnaHRcXH0gXFwpIFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWFjMDA/PFwvcD5cclxuXHJcbjxwPlx1Yzk5MFx1YWM3MFx1YzZiNCBcdWMwYzlcdWNlNjAgXHViYjM4XHVjODFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWQ1NjhcdWMyMTggXFwoZlxcKVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFxcKFUgPVxcbGVmdFxceyB4XzEseF8yLFxcZG90cyAsIHhfbiBcXHJpZ2h0XFx9ICZuYnNwO1xcKSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmU0OCBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWNmYyBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG1cdWFjMWMgXHVjOTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFxcKFNfaVxcKVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXFwoeF9pXFwpXHVjNzU4IGlcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEgJmxlOyBrICZsZTsgMTMsIDQgJmxlOyBuICZsZTsgMjIsIDYgJmxlOyBtICZsZTsgMTExPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTY4XHVjMjE4IFxcKGZcXClcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0ICYjMzk7WSYjMzk7XHViOTdjLCBcdWM1NDRcdWIyYzhcdWJhNzQgJiMzOTtOJiMzOTtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODE1XHViMmY1XHVjNzQwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViZDk5XHVjNWVjXHVjMTFjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTY0MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZ1biBDb2xvcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIHByb2JsZW0gY2FsbGVkIEZVTiBDT0xPUklORyBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RlVOIENPTE9SSU5HIFBST0JMRU0mbmJzcDs8XC9wPlxyXG5cclxuPHA+SU5TVEFOQ0U6IEEgZmluaXRlIHNldCBcXChVXFwpIGFuZCBzZXRzIFxcKFNfMSxTXzIsU18zLFxcZG90cyAsU19tIFxcc3Vic2V0ZXEgVSBcXCkgYW5kICZuYnNwO1xcKFxcbGVmdHwgU19pIFxccmlnaHR8ICZuYnNwOyBcXGxlIDNcXCk8XC9wPlxyXG5cclxuPHA+UFJPQkxFTTogSXMgdGhlcmUgYSBmdW5jdGlvbiBcXChmOlVcXG1hcHN0byBcXGxlZnRcXHsgUkVELEJMVUUgXFxyaWdodFxcfSBcXCkgc3VjaCB0aGF0IGF0IGxlYXN0IG9uZSBtZW1iZXIgb2YgZWFjaCBcXChTX2lcXCkgaXMgYXNzaWduZWQgYSBkaWZmZXJlbnQgY29sb3IgZnJvbSB0aGUgb3RoZXIgbWVtYmVycz8mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW5zdGFuY2Ugb2YgRlVOIENPTE9SSU5HIFBST0JMRU0sIHlvdXIgam9iIGlzIHRvIGZpbmQgb3V0IHdoZXRoZXIgc3VjaCBmdW5jdGlvbiBcXChmXFwpIGV4aXN0cyBmb3IgdGhlIGdpdmVuIGluc3RhbmNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhpcyBwcm9ibGVtIFxcKFUgPVxcbGVmdFxceyB4XzEseF8yLFxcZG90cyAsIHhfbiBcXHJpZ2h0XFx9ICZuYnNwO1xcKS4gVGhlcmUgYXJlIGsgaW5zdGFuY2VzIG9mIHRoZSBwcm9ibGVtLiBUaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIGsgYW5kIHRoZSBmb2xsb3dpbmcgbGluZXMgZGVzY3JpYmUgayBpbnN0YW5jZXMsIGVhY2ggaW5zdGFuY2Ugc2VwYXJhdGVkIGJ5IGEgYmxhbmsgbGluZS4gSW4gZWFjaCBpbnN0YW5jZSB0aGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgbSB3aXRoIGEgYmxhbmsgaW4gYmV0d2Vlbi4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHNvbWUgaW50ZWdlcnMgaSZyc3F1bztzIHJlcHJlc2VudGluZyBcXCh4X2lcXCkmcnNxdW87cyBpbiBcXChTXzFcXCksIGVhY2ggaSBzZXBhcmF0ZWQgYnkgYSBibGFuay4gVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgc29tZSBpbnRlZ2VycyBpJnJzcXVvO3MgcmVwcmVzZW50aW5nIFxcKHhfaVxcKSZyc3F1bztzIGluIFxcKFNfMlxcKSBhbmQgc28gb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBsaW5lIG0rMiBjb250YWlucyBzb21lIGludGVnZXJzIGkmcnNxdW87cyByZXByZXNlbnRpbmcgXFwoeF9pXFwpJnJzcXVvO3MgaW4gXFwoU19tXFwpLiBGb2xsb3dpbmcgYSBibGFuayBsaW5lLCB0aGUgc2Vjb25kIGluc3RhbmNlIG9mIHRoZSBwcm9ibGVtIGlzIGRlc2NyaWJlZCBpbiB0aGUgc2FtZSBtYW5uZXIgYW5kIHNvIG9uIHVudGlsIHRoZSBrPHN1cD50aDxcL3N1cD4gaW5zdGFuY2UgaXMgZGVzY3JpYmVkLjxcL3A+XHJcblxyXG48cD5JbiBhbGwgdGVzdCBjYXNlcywgMSAmbGU7IGsgJmxlOyAxMywgNCAmbGU7IG4gJmxlOyAyMiwgYW5kIDYgJmxlOyBtICZsZTsgMTExLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGluc3RhbmNlIG9mIHRoZSBwcm9ibGVtLCBpZiBcXChmXFwpIGV4aXN0cywgcHJpbnQgYSBZLiBPdGhlcndpc2UsIHByaW50IE4uIFlvdXIgc29sdXRpb24gd2lsbCBjb250YWluIG9uZSBsaW5lIG9mIGsgWSZyc3F1bztzIChvciBOJnJzcXVvO3MpIHdpdGhvdXQgYSBibGFuayBpbiBiZXR3ZWVuLiBUaGUgZmlyc3QgWSAob3IgTikgaXMgdGhlIHNvbHV0aW9uIGZvciBpbnN0YW5jZSAxLiBUaGUgc2Vjb25kIFkgKG9yIE4pIGlzIHRoZSBzb2x1dGlvbiBmb3IgaW5zdGFuY2UgMiwgYW5kIHNvIG9uLiBUaGUgbGFzdCBZIChvciBOKSBpcyB0aGUgc29sdXRpb24gZm9yIGluc3RhbmNlIGsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest C번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013