Problems
Fun Coloring
Fun Coloring
Consider the problem called Fun Coloring below.
Fun Coloring Problem
Instance: A finite set \textbf{U} and sets \textbf{S_1}, \textbf{S_2}, \textbf{S_3}, … , \textbf{S_m} \textbf{U} and |\textbf{S_i}| ≤ \textbf{3}.
Problem: Is there a function \textbf{f}: \textbf{U \{RED, BLUE\}} such that at least one member of each\textit{ S_i} is assigned a different color from the other members?
Given an instance of Fun Coloring Problem, your job is to find out whether such function \textbf{f} exists for the given instance.
\InputFile
In this problem \textbf{U = \{x_1, x_2, x_3,…,x_n\}}. There are \textbf{k} instances of the problem. The first line of the input file contains a single integer \textbf{k} and the following lines describe \textbf{k} instances, each instance separated by a blank line. In each instance the first line contains two integers \textbf{n}\textit{ }and\textit{ }\textbf{m} with a blank in between. The second line contains some integers\textit{ }\textbf{i}’srepresenting \textbf{x_i}’s\textit{ }\textbf{in S_1}, each \textbf{i} separated by a blank. The third line contains some integers\textit{ }\textbf{i}’s representing \textbf{x_i}’s\textit{ }\textbf{in S_2} and so on. The line \textbf{m+2} contains some integers\textit{ }\textbf{i}’s representing \textbf{x}_i’s\textbf{ in S}_m. Following a blank line, the second instance of the problem is described in the same manner and so on until the \textbf{k}^th instance is described. In all test cases, \textbf{1} ≤ \textbf{k} ≤ \textbf{13},\textbf{4} ≤ \textbf{n} ≤ \textbf{22}, and \textbf{6} ≤ \textbf{m} ≤ \textbf{111}.
\OutputFile
For each instance of the problem, if \textbf{f} exists, print a \textbf{Y}. Otherwise, print \textbf{N}. Your solution will contain one line of \textbf{k} \textbf{Y}’s(or \textbf{N}’s) without a blank in between. The first \textbf{Y} (or \textbf{N}) is the solution for instance \textbf{1}. The second \textbf{Y} (or \textbf{N}) is the solution for instance \textbf{2}, and so on. The last \textbf{Y} (or \textbf{N}) is the solution for instance \textbf{k}.
Input example #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
Output example #1
YN