CF1494E A-Z Graph

给定一个包含 $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，否则输出 NO。

对于第一个第三种类型的操作，$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$。 由 ChatGPT 4.1 翻译