Codeforces Round 805 (Div. 3) |
---|
Закончено |
Поликарпу недавно подарили набор из $$$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 и NO в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
641 24 32 13 461 24 51 34 62 35 621 12 221 22 182 11 24 34 35 65 78 67 881 22 14 35 35 46 78 67 8
YES NO NO YES YES NO
В первом наборе входных данных костяшки можно разделить так:
Во втором наборе входных данных как костяшки не раздели на $$$2$$$ набора, хотя бы в одном будут повторяющиеся числа.
Название |
---|