1352: Обмін


Відправити розв'язок


Бали:5
Time limit:0.5s
Python2.0s
Memory limit:63M
Python500M
Author:

Problem type

Ваша неприбуткова організація координує програму з обміну студентами. І їй потрібна Ваша допомога. Програма обміну працює наступним чином. Кожен із учасників надає інформацію про місце свого мешкання та місце, куди він бажає переїхати. Програма вважається успішною, якщо кожний студент знайде для обміну відповідного партнера. Іншими словами, якщо студент бажає переїхати з A в B, то обов'язково має існувати інший студент, який бажає переїхати з B в A. Це проста задача, якщо учасників програми не більше 10. Але що робити якщо їх буде 100001?

Формат вхідних даних

Перший рядок містить кількість тестів t. Перший рядок кожного тесту містить кількість студентів n (1 ≤ n ≤ 100001), за яким йдуть n рядків, що описують дані з обміну. Кожний з цих рядків містить інформацію про одного студента - два цілі числа, розділені проміжком, що відповідають поточному місцю мешкання студента та місцю, куди він бажає переїхати. Місця описуються невід'ємними цілими числами, не більшими за 109. У жодного з кандидатів місце мешкання не співпадає з місцем переїзду.

Формат вихідних даних

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

Приклад вхідних даних

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

Приклад вихідних даних

YES
NO

Коментарі


  • 0
    Aradam
     прокоментував о Липень 12, 2018

    Time Limit Python.


    • 0
      zvit
       прокоментував о Сер. 8, 2018

      час збільшено...