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