학회 원탁

KAIST에서 학회가 열린다. 이 학회에는 대한민국 각 대학에서 가장 뛰어난 연구자 두 명씩이 초대된다. 한 대학에서 온 두 연구자는 전공이 같을 수도 있고 서로 다를 수도 있다. 조직위원회는 모든 연구자를 하나의 큰 원탁에 둘러앉혀야 한다.

학회가 시작되면 각 대학의 두 연구자는 자신의 양옆에 앉은 사람들에게 자신을 소개한다. 그래서 같은 대학에서 온 두 연구자는 반드시 서로 옆자리에 앉아야 한다. 또한 학회 도중 연구자들은 다른 대학의 같은 전공 연구자와 자신의 연구를 논의하고 싶어할 수 있다. 따라서 서로 다른 대학에서 왔지만 옆자리에 앉는 두 연구자는 같은 전공을 공유하는 것이 바람직하다.

다음 두 조건을 모두 만족하는 자리 배치가 존재하는지 판단하여라.

1. 각 대학의 두 연구자는 서로 옆자리에 앉는다.
2. 옆자리에 앉은 모든 연구자 쌍은 같은 대학 소속이거나 같은 전공을 공유한다.

아래 그림은 두 조건을 모두 만족하는 자리 배치의 한 예이다.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫째 줄에는 학회에 참가하는 대학의 수 $N$ ($1 \le N \le 2000$)이 주어진다. 모든 대학은 서로 다르다. 이어지는 $N$개의 줄에는 각각 두 정수 $X$, $Y$ ($1 \le X, Y \le 40$)가 주어지며, 이는 한 대학에서 온 두 연구자의 전공을 나타낸다.

각 테스트 케이스마다 정확히 한 줄을 출력한다. 조건을 만족하는 자리 배치가 가능하면 "YES"를, 불가능하면 "NO"를 출력한다.