Задача №2786. Разрезание графа
Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
-
cut— разрезать граф, то есть удалить из него ребро; -
ask— проверить, лежат ли две вершины графа в одной компоненте связности.
Известно, что после выполнения всех операций типа cut рёбер в графе
не осталось. Найдите результат выполнения каждой из операций типа ask.
Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа \(n\), количество рёбер \(m\) и количество операций \(k\) (\(1 \le n \le 50\,000\), \(0 \le m \le 100\,000\), \(m \le k \le 150\,000\)).
Следующие \(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 во входном файле.
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