Весела розмальовка
Розгляньмо задачу під назвою "Весела розфарбовка".
Задача "Весела розфарбовка"
Дано: Кінцева множина U і підмножини S_1, S_2, S_3, … , S_m, де S_i ⊆ U і |S_i| ≤ 3.
Завдання: Чи існує функція f: U → {RED, BLUE}, така, що в кожній множині S_i хоча б один елемент має колір, відмінний від інших?
Вам надано екземпляр задачі "Весела розфарбовка", і ваше завдання — визначити, чи існує така функція f для даного екземпляра.
Вхідні дані
У цій задачі U = {x_1, x_2, x_3,…,x_n}. Дано k екземплярів задачі. Перший рядок вхідного файлу містить одне ціле число k, а наступні рядки описують k екземплярів, кожен з яких відділений порожнім рядком. У кожному екземплярі перший рядок містить два цілі числа n і m, розділені пробілом. Другий рядок містить деякі цілі числа i, що представляють x_i в S_1, кожне i відділене пробілом. Третій рядок містить деякі цілі числа i, що представляють x_i в S_2, і так далі. Рядок m+2 містить деякі цілі числа i, що представляють x_i в S_m. Після порожнього рядка другий екземпляр задачі описується аналогічним чином, і так продовжується, поки не буде описано k-й екземпляр. У всіх тестах 1 ≤ k ≤ 13, 4 ≤ n ≤ 22, і 6 ≤ m ≤ 111.
Вихідні дані
Для кожного екземпляра задачі, якщо функція f існує, виведіть Y. В іншому випадку виведіть N. Ваше рішення повинно містити один рядок з k символів Y або N без пробілів між ними. Перший символ Y або N є рішенням для першого екземпляра, другий — для другого, і так далі. Останній символ Y або N є рішенням для k-го екземпляра.