У вас есть ориентированный граф, состоящий из $$$n$$$ вершин. Каждое ориентированное ребро (дуга) помечено одной буквой. Первоначально, граф пустой.
Вам нужно обработать $$$m$$$ запросов на нем. Каждый запрос одного из трех типов:
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин в графе и количество запросов.
В следующих $$$m$$$ строках заданы сами запросы — по одному в строке. Каждый запрос одного из трех типов:
Гарантируется, что вы не добавляете кратные ребра и удаляете только существующие ребра. Также в тесте есть хотя бы один запрос третьего типа.
Для каждого запроса третьего типа, выведите 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$$$.
Название |
---|