Веселая раскраска
Рассмотрим задачу под названием "Веселая раскраска".
Задача "Веселая раскраска"
Дано: Конечное множество 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-го экземпляра.