A-Z Graph
Contest: Educational Codeforces Round 105 (Rated for Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, data structures, graphs, hashing

You are given a directed graph consisting of $$$n$$$ vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty.

You should process $$$m$$$ queries with it. Each query is one of three types:

- "$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$" — add arc from $$$u$$$ to $$$v$$$ with label $$$c$$$. It's guaranteed that there is no arc $$$(u, v)$$$ in the graph at this moment;
- "$$$-$$$ $$$u$$$ $$$v$$$" — erase arc from $$$u$$$ to $$$v$$$. It's guaranteed that the graph contains arc $$$(u, v)$$$ at this moment;
- "$$$?$$$ $$$k$$$" — find the sequence of $$$k$$$ vertices $$$v_1, v_2, \dots, v_k$$$ such that there exist both routes $$$v_1 \to v_2 \to \dots \to v_k$$$ and $$$v_k \to v_{k - 1} \to \dots \to v_1$$$ and if you write down characters along both routes you'll get the same string. You can visit the same vertices any number of times.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — the number of vertices in the graph and the number of queries.

The next $$$m$$$ lines contain queries — one per line. Each query is one of three types:

- "$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$" ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$c$$$ is a lowercase Latin letter);
- "$$$-$$$ $$$u$$$ $$$v$$$" ($$$1 \le u, v \le n$$$; $$$u \neq v$$$);
- "$$$?$$$ $$$k$$$" ($$$2 \le k \le 10^5$$$).

It's guaranteed that you don't add multiple edges and erase only existing edges. Also, there is at least one query of the third type.

Output format:
For each query of the third type, print YES if there exist the sequence $$$v_1, v_2, \dots, v_k$$$ described above, or NO otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first query of the third type $$$k = 3$$$, we can, for example, choose a sequence $$$[1, 2, 3]$$$, since $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3$$$ and $$$3 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 1$$$.

In the second query of the third type $$$k = 2$$$, and we can't find sequence $$$p_1, p_2$$$ such that arcs $$$(p_1, p_2)$$$ and $$$(p_2, p_1)$$$ have the same characters.

In the third query of the third type, we can, for example, choose a sequence $$$[1, 2, 3, 2, 1]$$$, where $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3 \xrightarrow{\text{d}} 2 \xrightarrow{\text{c}} 1$$$.

Example input:
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

Example output:
YES
NO
YES

Editorial:
At first, if there should be both routes $$$v_1, v_2, \dots, v_k$$$ and $$$v_k, v_{k - 1}, \dots, v_1$$$ then there are both arcs $$$(v_1, v_2)$$$ and $$$(v_2, v_1)$$$, i. e. there should exist at least one pair $$$\{u, v\}$$$ that both arcs $$$(u, v)$$$ and $$$(v, u)$$$ are present in the graph.
Now, if $$$k$$$ is odd, and we have at least one pair $$$\{u, v\}$$$ then we can simply create sequence $$$u, v, u, v, \dots, v, u$$$. This sequence is a palindrome so, obviously, both routes generate the same string.
If $$$k$$$ is even (or $$$k = 2x$$$), we can note that in the sequence $$$v_1, v_2, \dots, v_{2x}$$$ there is a middle arc $$$(v_x, v_{x + 1})$$$ and it should have the same character as arc $$$(v_{x + 1}, v_x)$$$ (since it's a middle arc in reverse route $$$v_k, \dots, v_1$$$), i. e. there should exist at least one pair $$$\{u, v\}$$$ that both arcs $$$(u, v)$$$ and $$$(v, u)$$$ are present in the graph and have the same label.
Now, if we have at least one such pair $$$\{u, v\}$$$ then routes $$$u, v, \dots, u, v$$$ and $$$v, u, \dots, v, u$$$ generate the same one-letter strings.
Since each arc $$$(u, v)$$$ is a part of at most one pair $$$\{u, v\}$$$, we can just maintain two sets with pairs $$$\{u, v\}$$$: one for pairs with different labels and the other one for pairs with equal labels. If $$$k$$$ is odd, we check that at least one of the sets is not empty. If $$$k$$$ is even, we check that the second set is not empty.