E. A-Z граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть ориентированный граф, состоящий из $$$n$$$ вершин. Каждое ориентированное ребро (дуга) помечено одной буквой. Первоначально, граф пустой.

Вам нужно обработать $$$m$$$ запросов на нем. Каждый запрос одного из трех типов:

  • «$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$» — добавить дугу из $$$u$$$ в $$$v$$$ с меткой $$$c$$$. Гарантируется, что в данный момент в графе нет дуги $$$(u, v)$$$;
  • «$$$-$$$ $$$u$$$ $$$v$$$» — удалить дугу из $$$u$$$ в $$$v$$$. Гарантируется, что в данный момент в графе есть дуга $$$(u, v)$$$;
  • «$$$?$$$ $$$k$$$» — найти последовательность из $$$k$$$ вершин $$$v_1, v_2, \dots, v_k$$$ такую, что существуют и маршрут $$$v_1 \to v_2 \to \dots \to v_k$$$, и маршрут $$$v_k \to v_{k - 1} \to \dots \to v_1$$$, и если вы выпишите буквы вдоль обоих маршрутов, вы получите одинаковые строки. Вы можете посещать одни и те же вершины любое количество раз.
Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин в графе и количество запросов.

В следующих $$$m$$$ строках заданы сами запросы — по одному в строке. Каждый запрос одного из трех типов:

  • «$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$» ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$c$$$ — строчная буква латинского алфавита);
  • «$$$-$$$ $$$u$$$ $$$v$$$» ($$$1 \le u, v \le n$$$; $$$u \neq v$$$);
  • «$$$?$$$ $$$k$$$» ($$$2 \le k \le 10^5$$$).

Гарантируется, что вы не добавляете кратные ребра и удаляете только существующие ребра. Также в тесте есть хотя бы один запрос третьего типа.

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

Для каждого запроса третьего типа, выведите YES, если существует последовательность $$$v_1, v_2, \dots, v_k$$$, описанная выше, иначе выведите NO.

Пример
Входные данные
3 11
+ 1 2 a
+ 2 3 b
+ 3 2 a
+ 2 1 b
? 3
? 2
- 2 1
- 3 2
+ 2 1 c
+ 3 2 d
? 5
Выходные данные
YES
NO
YES
Примечание

В первом запросе третьего типа $$$k = 3$$$, и мы можем, например, выбрать последовательность $$$[1, 2, 3]$$$, так как $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3$$$ и $$$3 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 1$$$.

Во втором запросе третьего типа $$$k = 2$$$, и мы не можем выбрать такую последовательность $$$p_1, p_2$$$, что дуги $$$(p_1, p_2)$$$ и $$$(p_2, p_1)$$$ имеют одинаковые метки.

В третьем запросе третьего типа, мы можем, например, выбрать последовательность $$$[1, 2, 3, 2, 1]$$$, где $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3 \xrightarrow{\text{d}} 2 \xrightarrow{\text{c}} 1$$$.