Processing math: 13%

Задача C2. Разрезание графа

Входной файл:cutting.in   Ограничение времени:2 сек
Выходной файл:cutting.out   Ограничение памяти:256 Мб

Условие

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

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

Формат входного файла

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа n, количество рёбер m и количество операций k (1, 0 \leqslant m \leqslant 100\,000, m \leqslant k \leqslant 150\,000).

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

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

Формат выходного файла

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

Ограничения

Примеры тестов

Входной файл (cutting.in) Выходной файл (cutting.out)
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
YES
YES
NO
NO

0.049s 0.007s 13