eolymp
bolt
Try our new interface for solving problems
Məsələlər

Обмен иностранцами

Обмен иностранцами

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Ваша неприбыльная организация координирует программу по обмену студентами. И ей нужна Ваша помощь.

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из A в B, то обязательно должен быть другой студент, который хочет переехать из B в A. Это простая задача, если участников программы всего 10. Но что делать если их будет 100001?

Giriş verilənləri

Первая строка содержит количество тестов t. Первая строка каждого теста содержит количество студентов n (1n100001), за которыми следуют n строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте - два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими 10^9. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

Çıxış verilənləri

Для каждого теста в отдельной строке вывести "YES" если существует возможность успешно выполнить программу обмена и "NO" иначе.

Nümunə

Giriş verilənləri #1
2
10
1 2
2 1
3 4
4 3
100 200
200 100
57 2
2 57
1 2
2 1
10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
Çıxış verilənləri #1
YES
NO