G. Shareefeh's Zahreyye's Jewelry
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Shareefeh noticed a box in her room that belonged to Abu Shehab's ex-wife, Zahreyye. The box was filled with her jewelry. Feeling jealous, Shareefeh convinced Abu Shehab to throw it away. However, she soon felt guilty and begged Abu Shehab to retrieve the box so she could wear the jewelry herself.

Wanting to add a personal touch, Abu Shehab decided to design a custom necklace for Shareefeh. The necklace would be crafted using $$$n$$$ gemstones, each consisting of two halves — each half having its own color (both halves could even share the same color).

To make the necklace truly special, Abu Shehab asked Shareefeh's sister, Motee3a, for her favorite colors. Motee3a provided $$$n$$$ pairs of color preferences, each pair representing possible colors for a single gemstone.

Shareefeh with one of the Abu Shehab's ex-wife necklace .

Abu Shehab then went to Souq Al-Hamidiyah and bought $$$n$$$ gemstones according to these preferences.

Afterward, he visited Khater's jewelry store, handed over the $$$n$$$ gemstones, and asked Khater to assemble a necklace. Khater would start with a chain and sequentially insert each gemstone into it. He could insert each gemstone from either side. Finally, after inserting the last gemstone, he would close the chain, making the necklace a continuous loop where the first gemstone is adjacent to the last.

Abu Shehab had only one request: the necklace must be formed so that each color appears in at most one continuous segment (i.e., every color, if present, should appear in a single uninterrupted block in the necklace cycle).

Can you help Khater determine whether this is possible and deliver the answer to Abu Shehab as soon as possible?

Input

The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.

For each test case:

The first line of input will contain one integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ — denotes the number of sides for the stone and the number of Shareefeh's preferences.

The next $$$n$$$ lines contain two integers each, the i-th of them contains two space-separated integers $$$a_i$$$ and $$$b_i$$$ $$$( 1 \le a_i , b_i \le 2 \cdot n)$$$ — the i-th pair denotes the two colors that Shareefeh prefers.

It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print "Yes" if Khater can create such jewel, print "NO" otherwise.

You can output the answer in any case. For example, the strings "yEs", "yes", and "YES" will also be recognized as positive responses.

Example
Input
3
6
1 1
1 2
3 3
3 4
4 4
2 2
1
1 2
3
1 2
1 3
1 4
Output
Yes
Yes
No
Note

First example:

Let:

$$$1$$$ —> Yellow,

$$$2$$$ —> Green,

$$$3$$$ —> Red,

$$$4$$$ —> Blue,

The picture is: