Вибори#8494

Вибори

3 секунди

128 мегабайтів

Легка

У найближчий час у Берляндії відбудуться нові парламентські вибори. Кожна з $n$ політичних партій прагне бути обраною до парламенту. У Берляндії діє закон, що дозволяє обирати лише ті партії, які отримали більше певної кількості голосів. Тому деякі малі партії намагаються використовувати різні технології, щоб зібрати необхідну кількість голосів.

Перша технологія є цілком законною. Дві або більше партій можуть об'єднатися для участі у виборах, утворюючи так званий виборчий блок.

Друга технологія не така легальна. Деякі партії володіють специфічною інформацією про своїх опонентів, які не хочуть, щоб ця інформація стала загальнодоступною.

Якщо кілька партій об'єднуються в один виборчий блок, їхня інформація також об'єднується, що робить їх сильнішими. Проте опоненти кожної партії блоку знають щось дискредитуюче про весь блок. Партія або блок можуть мати певну "чорну" інформацію про себе.

Пронумеруємо партії натуральними числами від $1$ до $n$ . Партіям і блокам дозволено об'єднуватися в нові блоки, які будуть нумеруватися послідовними натуральними числами ( $n + 1$ n + 1, $n + 2$ n + 2, і так далі).

Вам потрібно написати програму, яка обробляє запити двох типів:

Запит $1$ $a$ $b$ : чи існує якась дискредитуюча інформація, якою володіє партія або блок $a$ про партію або блок $b$ ?
Запит $2$ $a$ $b$ означає, що слід об'єднати партію або блок $a$ з партією або блоком $b$ . Новий блок буде володіти інформацією як блоку $a$ , так і блоку $b$ . Вся інформація, відома деяким сторонам або блокам про $a$ і $b$ , тепер стосується новоствореного блоку.

Вхідні дані

Перший рядок містить числа $n$ і $m$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100\,000, $1 \leq m \leq 200000$ 1 \leq m \leq 200\,000). Кожен з наступних $m$ рядків містить пару цілих чисел $a$ і $b$ , що вказують на те, що група $a$ володіє деякими дискредитуючими знаннями про групу $b$ ( $1 \leq a, b \leq n$ 1 \leq a, b \leq n). Наступний рядок містить число $q$ ( $1 \leq q \leq 200000$ 1 \leq q \leq 200\,000). Кожен з наступних $q$ рядків містить запит. Запит першого типу виглядає як $1$ $a$ $b$ . Запит другого типу виглядає як $2$ $a$ $b$ . Ви повинні обробляти запити в тому порядку, в якому вони вказані. Кожна пара $a$ , $b$ посилається лише на існуючі партії та блоки. Гарантується, що $a$ і $b$ різні в будь-якому запиті $2$ $a$ $b$ , але вони можуть бути однакові в запиті $1$ $a$ $b$ .

Вихідні дані

Виведіть в окремому рядку YES або NO для кожного запиту першого виду.

Приклади

Приклад 1