CF1494E.A-Z Graph

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.

给你一个包含 $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$，且沿这两条路径依次读取边上的字符所构成的字符串完全相同。允许重复访问同一顶点任意多次。

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.

第一行包含两个整数 $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$）。

保证不会添加重复的边，且仅删除已存在的边。此外，至少存在一个第三类查询。

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.

对于每个第三种类型的查询，如果存在上述描述的序列 $v_1, v_2, \dots, v_k$，则输出 YES；否则输出 NO。

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$.

在第三个类型的第一次查询中，$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$。