Fun Coloring
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_mU 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.
Giriş verilənləri
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 nandm with a blank in between. The second line contains some integersi’srepresenting x_i’sin S_1, each i separated by a blank. The third line contains some integersi’s representing x_i’sin S_2 and so on. The line m+2 contains some integersi’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.
Çıxış verilənləri
For each instance of the problem, if f exists, print a Y. Otherwise, print N. Your solution will contain one line of kY’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.
Nümunə
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
YN