F :: Fun Coloring

Time Limit: 10 Seconds Memory Limit: 65536 KB

Consider the problem called FUN COLORING below.

-=FUN COLORING PROBLEM=-
INSTANCE: A finite set U and sets S1, S2, S3,…,Sm ⊆ U and |Si| ≤ 3. PROBLEM: Is there a function f : U ->{RED, BLUE} such that at least one member of each Si 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 = {x1, x2, x3,…,xn}. 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’s representing xi’s in S1, each i separated by a blank. The third line contains some integers i’s representing xi’s in S2 and so on. The line m+2 contains some integers i’s representing xi’s in Sm. Following a blank line, the second instance of the problem is described in the same manner and so on until the kth 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.

Sample Input

Sample Output

YN

Submit