← 返回题目列表

Codeforces · 1494/E

E. A-Z 图

中文机器翻译题面 查看原题

给你一个由 $$$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$$$。