eolymp

Розрізання графа

Задано неорієнтовний граф. Над ним у заданом порядку виконуються операції наступних двох типів:

  • cut - розрізати граф, тобто видалити з нього ребро;
  • ask - перевірити, чи лежать дві вершини графа у одній компоненті зв'язності.

Відомо, що після виконання усіх операцій типу cut ребер в графі не залишилось. Знайдіть результат виконання кожної з операцій типу ask.

Вхідні дані

Перший рядок містить три цілих числа, відокремлені пропусками - кількість вершин графа n, кількість ребер m та кількість операцій k (1n50000, 0m100000, mk150000).

Наступні m рядків задають ребра графа; i-й з цих рядків містить два числа ui та vi (1ui, vin), відокремлені пропусками - номери кінців i-го ребра. Вершини нумеруються з одиниці; граф не містить кратних ребер та петель.

Далі йде k рядків, які описують операції. Операція типу cut задається рядком "cut u v" (1u, vn), який означає. що з графа видаляють ребро між вершинами u та v. Операція типу ask задається рядком "ask u v" (1u, vn), який означає, що необхідно взнати, чи лежать у даний момент вершини u та v в одній компоненті зв'язності. Гарантується, що кожне ребро графа зустрінеться в операціях типу cut рівно один раз.

Вихідні дані

Для кожної операції ask виведіть у окремому рядку слово "YES", якщо дві вказані вершини лежать у одній компоненті зв'язності, і "NO" у протилежному випадку. Порядок відповідей повинен відповідати порядку операцій ask у вхідних даних.

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
Вихідні дані #1
YES
YES
NO
NO