E. Раздели на два набора
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарпу недавно подарили набор из $$$n$$$ (число $$$n$$$ — чётное) костяшек домино. На каждой костяшке написаны два целых числа от $$$1$$$ до $$$n$$$.

Сможет ли он разделить все костяшки на два набора так, чтобы все числа на костяшках каждого набора были различны? Каждая костяшка должна войти ровно в один из двух наборов.

Например, если у него есть $$$4$$$ костяшки: $$$\{1, 4\}$$$, $$$\{1, 3\}$$$, $$$\{3, 2\}$$$ и $$$\{4, 2\}$$$, то Поликарп сможет разделить их на два набора требуемым образом. В первый набор может войти первая и третья костяшка ($$$\{1, 4\}$$$ и $$$\{3, 2\}$$$), а во второй — вторая и четвёртая ($$$\{1, 3\}$$$ и $$$\{4, 2\}$$$).

Входные данные

В первой строке записано единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных содержится единственное целое чётное число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество костяшек.

В следующих $$$n$$$ строках содержатся пары чисел $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), описывающие числа на $$$i$$$-й костяшке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных в тесте не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите:

  • YES, если возможно разделить $$$n$$$ костяшек на два набора так, что числа на костяшках каждого набора различны;
  • NO, если сделать это невозможно.

Вы можете выводить YES и NO в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).

Пример
Входные данные
6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8
Выходные данные
YES
NO
NO
YES
YES
NO
Примечание

В первом наборе входных данных костяшки можно разделить так:

  • Первый набор: $$$[\{1, 2\}, \{4, 3\}]$$$
  • Второй набор: $$$[\{2, 1\}, \{3, 4\}]$$$
Иными словами в первый набор берём костяшки с номерами $$$1$$$ и $$$2$$$, а во второй набор берём костяшки с номерами $$$3$$$ и $$$4$$$.

Во втором наборе входных данных как костяшки не раздели на $$$2$$$ набора, хотя бы в одном будут повторяющиеся числа.