Задачи
Magic Graphs
Magic Graphs
A \textbf{k}-partite graph is a graph whose vertices can be partitioned into \textbf{K} disjoint sets so that no two vertices within the same set are adjacent. In this problem we consider a special version of a \textbf{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.
\includegraphics{https://static.e-olymp.com/content/cc/cc8a15c4c87b4c7e92efe076a394dd47b084fd99.jpg}
Let \textbf{P} be a set of positive labels \textbf{\{1, 2, 3, 4, …\}} and \textbf{N} be a set of negative labels \textbf{\{1', 2', 3', 4',…\}}. Also let \textbf{L = P} U \textbf{N}. A magic graph is a k-partite graph \textbf{G = (V, E)}, where \textbf{V} is a set of vertices and E is a set of edges. We define\textbf{V = V_1} U \textbf{V_2} U \textbf{V_3} U … U \textbf{V_k}, where each \textbf{V_i} \textbf{L} and \textbf{|V_i| = 2}. There is an edge \textbf{\{l_1, l_2\}} in \textbf{G} if and only if \textbf{l_1} and \textbf{l_2} are in different vertex sets and \textbf{l_1} and \textbf{l_2} are not positive and negative labels of the same number. For instance, the following graph is a magic graph.
\includegraphics{https://static.e-olymp.com/content/40/4032c5f80326c65f6fc6b052eaacf51dfc702191.jpg}
This graph is a tripartite magic graph. \textbf{V_1} is \textbf{\{1, 2\}}. \textbf{V_2} is \textbf{\{1', 2'\}}. \textbf{V_3} is \textbf{\{1, 2'\}}. Be noted that multiple nodes may have the same label. For example, the node labeled \textbf{1} in \textbf{V_1} is a not the same node as the node labeled \textbf{1} in \textbf{V_3}. The edges follow the rule above. For example, there are edges \textbf{\{1, 1\}} and \textbf{\{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 \textbf{\{1, 1'\}} does not exist because the two labels are positive and negative labels of the same number.
Given a \textbf{k}-partite magic graph \textbf{G}, your job is to find whether there exists a \textbf{k}-clique in \textbf{G}.
\InputFile
First line of input is a number of test cases \textbf{T} ≤ \textbf{10}. The format of each test case is as follow.
\begin{itemize}
\item The first line contains the integer \textbf{K} (\textbf{2} ≤ \textbf{K} ≤ \textbf{24000}).
\item The following \textbf{K} lines describe set \textbf{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.
\end{itemize}
\OutputFile
The output file contains only one line of strings of length \textbf{T} in \textbf{\{Y, N\}*}. That is, for each test case, if a given magic graph \textbf{G} has a \textbf{k}-clique, print \textbf{Y}, otherwise, print \textbf{N}.
Входные данные #1
2 3 1 2 -1 -2 1 -2 4 1 -2 1 2 -1 2 -1 -2
Выходные данные #1
YN