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

Magic Graphs

Magic Graphs

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

A k-partite graph is a graph whose vertices can be partitioned into K disjoint sets so that no two vertices within the same set are adjacent. In this problem we consider a special version of a k-partite graph in which each disjoint set contains exactly two vertices. Let us call this graph magic graph. In what follows we characterize such magic graphs.

Let P be a set of positive labels {1, 2, 3, 4, …} and N be a set of negative labels {1', 2', 3', 4',…}. Also let L = P U N. A magic graph is a k-partite graph G = (V, E), where V is a set of vertices and E is a set of edges. We defineV = V_1 U V_2 U V_3 U … U V_k, where each V_iL and |V_i| = 2. There is an edge {l_1, l_2} in G if and only if l_1 and l_2 are in different vertex sets and l_1 and l_2 are not positive and negative labels of the same number. For instance, the following graph is a magic graph.

This graph is a tripartite magic graph. V_1 is {1, 2}. V_2 is {1', 2'}. V_3 is {1, 2'}. Be noted that multiple nodes may have the same label. For example, the node labeled 1 in V_1 is a not the same node as the node labeled 1 in V_3. The edges follow the rule above. For example, there are edges {1, 1} and {1, 2'} because the labels are in different vertex sets and they are not positive and negative labels of the same number. Observe that edge {1, 1'} does not exist because the two labels are positive and negative labels of the same number.

Given a k-partite magic graph G, your job is to find whether there exists a k-clique in G.

Giriş verilənləri

First line of input is a number of test cases T10. The format of each test case is as follow.

  • The first line contains the integer K (2K24000).

  • The following K lines describe set V_i, one per line. For each line, there are two labels separated by a blank space. A positive label is represented by a positive number and a negative label by a minus sign and a positive number.

Çıxış verilənləri

The output file contains only one line of strings of length T in {Y, N}*. That is, for each test case, if a given magic graph G has a k-clique, print Y, otherwise, print N.

Nümunə

Giriş verilənləri #1
2
3
1 2
-1 -2
1 -2
4
1 -2
1 2
-1 2
-1 -2
Çıxış verilənləri #1
YN
Mənbə ACM ICPC Asia Thailand National programming Contest 2013