Conference Table

A conference is held at KAIST, where the top two researchers from every Korean university are invited. The two researchers from a university may study the same major or two different majors. The organizing committee must seat every researcher around one large round table.

When the conference begins, the two researchers from each university introduce themselves to the people sitting next to them, so the two researchers from the same university must sit next to each other. During the conference, researchers may want to discuss their work with researchers of the same major from other universities, so it is also desirable that any two researchers from different universities who sit next to each other share the same major.

Decide whether a seating arrangement exists that satisfies both of the following conditions:

1. The two researchers from each university sit next to each other.
2. Every pair of researchers sitting next to each other either come from the same university or share the same major.

The figure below shows one seating arrangement that satisfies both conditions.

The first line contains the number of test cases $T$ ($1 \le T \le 20$). Each test case is given as follows.

The first line of a test case contains an integer $N$ ($1 \le N \le 2000$), the number of universities taking part in the conference. All universities are distinct. Each of the next $N$ lines contains two integers $X$ and $Y$ ($1 \le X, Y \le 40$), the majors of the two researchers from one university.

For each test case, print exactly one line. Print "YES" if a valid seating arrangement exists, and "NO" otherwise.