eolymp
bolt
Try our new interface for solving problems
Məsələlər

Fun Coloring

Fun Coloring

Zaman məhdudiyyəti 10 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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, 1k13,4n22, and 6m111.

Çı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ə

Giriş verilənləri #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
Çıxış verilənləri #1
YN
Mənbə ACM-ICPC Asia Phuket Regional Programming Contest - 4 November 2011