Magic Graphs

A k-partite graph is a graph whose vertices split into $K$ disjoint sets so that no two vertices inside the same set are adjacent. This problem only deals with a special k-partite graph in which every set holds exactly two vertices. Call such a graph a magic graph.

Let $P = \{1, 2, 3, 4, \dots\}$ be the set of positive labels, let $N = \{1', 2', 3', 4', \dots\}$ be the set of negative labels, and let $L = P \cup N$. A magic graph is a k-partite graph $G = (V, E)$ with $V = V_1 \cup V_2 \cup \dots \cup V_K$, where every $V_i$ is a subset of $L$ with $|V_i| = 2$. The edge $\{l_1, l_2\}$ exists only when both conditions hold. First, $l_1$ and $l_2$ belong to different sets. Second, $l_1$ and $l_2$ are not the positive and the negative label of the same number.

For example, look at the tripartite magic graph with $V_1 = \{1, 2\}$, $V_2 = \{1', 2'\}$ and $V_3 = \{1, 2'\}$. Two vertices with the same label in different sets are different vertices, so the vertex labeled 1 in $V_1$ is not the vertex labeled 1 in $V_3$. The edges follow the rule above. The edges $\{1, 1\}$ and $\{1, 2'\}$ exist because the two labels sit in different sets and are not the positive and the negative label of one number. The edge $\{1, 1'\}$ does not exist, because 1 and $1'$ are the positive and the negative label of the same number.

Given a k-partite magic graph $G$, decide whether $G$ has a clique of size $K$.

The first line contains the number of test cases $T$, where $T \le 10$.

Each test case has the following format.

• The first line contains the integer $K$, where $2 \le K \le 24000$.
• Each of the next $K$ lines describes one set $V_i$ and holds two labels separated by a single space. A positive label is written as a positive number, and a negative label as a minus sign followed by a positive number.

Print one line with a string of length $T$ made of the characters Y and N. The $i$-th character answers the $i$-th test case: Y if the given magic graph has a clique of size $K$, and N otherwise.