매직 그래프

k-분 그래프는 정점 집합을 서로소인 $K$개의 집합으로 나눌 수 있고, 같은 집합에 속한 두 정점은 인접하지 않는 그래프다. 이 문제에서는 각 집합의 크기가 정확히 2인 특별한 k-분 그래프만 다루며, 이런 그래프를 매직 그래프라고 부른다.

양의 라벨 집합을 $P = \{1, 2, 3, 4, \dots\}$, 음의 라벨 집합을 $N = \{1', 2', 3', 4', \dots\}$라 하고 $L = P \cup N$이라 하자. 매직 그래프는 k-분 그래프 $G = (V, E)$이고, $V = V_1 \cup V_2 \cup \dots \cup V_K$이며 각 $V_i$는 $L$의 부분집합으로 $|V_i| = 2$다. 간선 $\{l_1, l_2\}$는 다음 두 조건을 모두 만족할 때만 존재한다. 첫째, $l_1$과 $l_2$가 서로 다른 집합에 속한다. 둘째, $l_1$과 $l_2$가 같은 수의 양의 라벨과 음의 라벨 관계가 아니다.

예를 들어 $V_1 = \{1, 2\}$, $V_2 = \{1', 2'\}$, $V_3 = \{1, 2'\}$인 3-분 매직 그래프를 보자. 라벨이 같아도 속한 집합이 다르면 다른 정점이다. $V_1$에서 라벨이 1인 정점과 $V_3$에서 라벨이 1인 정점은 서로 다른 정점이다. 간선은 위 규칙을 그대로 따른다. 간선 $\{1, 1\}$과 $\{1, 2'\}$는 두 라벨이 다른 집합에 있고 같은 수의 양음 라벨 쌍도 아니므로 존재한다. 반면 1과 $1'$은 같은 수의 양의 라벨과 음의 라벨이므로 간선 $\{1, 1'\}$은 없다.

k-분 매직 그래프 $G$가 주어질 때, $G$에 크기가 $K$인 클리크가 있는지 판정하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. $T \le 10$이다.

각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 정수 $K$가 주어진다. $2 \le K \le 24000$이다.
• 다음 $K$개의 줄에 집합 $V_i$가 한 줄에 하나씩 주어진다. 각 줄에는 라벨 두 개가 공백 하나로 구분되어 있다. 양의 라벨은 양수로 쓰고, 음의 라벨은 빼기 부호를 앞에 붙인 양수로 쓴다.

길이가 $T$이고 Y와 N으로 이루어진 문자열을 한 줄에 출력한다. $i$번째 문자는 $i$번째 테스트 케이스의 답이다. 주어진 매직 그래프에 크기가 $K$인 클리크가 있으면 Y, 없으면 N을 쓴다.