给你一个由 $$$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$$$)。
保证您不会添加多条边并仅删除现有边。另外,至少有一个第三类型的查询。
输出
对于第三种类型的每个查询,如果存在上述序列 $$$v_1, v_2, \dots, v_k$$$,则打印 YES,否则打印 NO。
示例
输入 #1
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
输出 #1
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$$$。