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

1000 мс · 256 МБ · всё или ничего

Над неориентированным графом выполняются операции двух видов: cut — удалить ребро, ask — проверить, лежат ли две вершины в одной компоненте связности. После всех операций рёбер не остаётся. Ответьте на все запросы ask.

Формат ввода

В первой строке $n$ , $m$ и $k$ ( $1 \le n \le 50\,000$ , $0 \le m \le 100\,000$ , $m \le k \le 150\,000$ ). Следующие $m$ строк задают рёбра парами $u_i$ , $v_i$ ; петель и кратных рёбер нет.

Следующие $k$ строк — операции вида cut u v или ask u v. Каждое ребро встречается в операциях cut ровно один раз.

Формат вывода

Для каждой операции ask выведите YES или NO в отдельной строке, в порядке следования запросов.

Примеры

ввод

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

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.