eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Разрезание графа

Разрезание графа

Лимит времени 3 секунды
Лимит использования памяти 128 MiB

Дан неориентированный граф. Над ним в заданном порядке производятся операции следующих двух типов:

  • cut — разрезать граф, то есть удалить из него ребро;

  • ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

Входные данные

Первая строка содержит три целых числа, разделённых пробелами — количество вершин графа n, количество рёбер m и количество операций k~ (1 \le n \le 50000, 0 \le m \le 10^5, m \le k ≤ 150000).

Следующие m строк задают рёбра графа; i-я из этих строк содержит два числа u_i и v_i~(1 \le u_i, v_i \le n) — номера концов i-го ребра. Вершины нумеруются с единицы; граф не содержит кратных рёбер и петель.

Далее следует k строк, описывающих операции. Операция типа cut задаётся строкой "cut u v" ~(1 \le u, v \le n), которая означает. что из графа удаляют ребро между вершинами u и v. Операция типа ask задаётся строкой "ask u v" ~(1 \le u, v \le n), которая означает, что необходимо узнать, лежат ли в данный момент вершины u и v в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

Выходные данные

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

Пример

Входные данные #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