{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给定一个由$$$n$$$个顶点组成的有向图。每条有向边(或弧)都标有一个单个字符。最初,图是空的。\u003c/p\u003e\u003cp\u003e你需要处理$$$m$$$个查询。每个查询有三种类型之一:\u003c/p\u003e\u003cul\u003e\u003cli\u003e“\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$\u003c/span\u003e”— 从$$$u$$$到$$$v$$$添加标记为$$$c$$$的弧。保证此时图中不存在弧$$$(u, v)$$$;\u003c/li\u003e\u003cli\u003e“\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$-$$$ $$$u$$$ $$$v$$$\u003c/span\u003e”— 从$$$u$$$到$$$v$$$删除弧。保证此时图中包含弧$$$(u, v)$$$;\u003c/li\u003e\u003cli\u003e“\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$?$$$ $$$k$$$\u003c/span\u003e”— 找到$$$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$$$,并且如果你沿着这两条路径写下字符,你会得到相同的字符串。你可以访问相同的顶点任意次数。\u003c/li\u003e\u003c/ul\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含两个整数$$$n$$$和$$$m$$$($$$2 \\le n \\le 2 \\cdot 10^5$$$;$$$1 \\le m \\le 2 \\cdot 10^5$$$)— 图中顶点的数量和查询的数量。\u003c/p\u003e\u003cp\u003e接下来的$$$m$$$行包含查询,每行一个。每个查询有三种类型之一:\u003c/p\u003e\u003cul\u003e\u003cli\u003e“\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$\u003c/span\u003e”($$$1 \\le u, v \\le n$$$;$$$u \\neq v$$$;$$$c$$$是小写拉丁字母);\u003c/li\u003e\u003cli\u003e“\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$-$$$ $$$u$$$ $$$v$$$\u003c/span\u003e”($$$1 \\le u, v \\le n$$$;$$$u \\neq v$$$);\u003c/li\u003e\u003cli\u003e“\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$?$$$ $$$k$$$\u003c/span\u003e”($$$2 \\le k \\le 10^5$$$)。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e保证你不会添加多条边,只会删除已存在的边。此外,至少有一个第三种类型的查询。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个第三种类型的查询,如果存在上述描述的序列$$$v_1, v_2, \\dots, v_k$$$,则打印\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e,否则打印\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 11\n+ 1 2 a\n+ 2 3 b\n+ 3 2 a\n+ 2 1 b\n? 3\n? 2\n- 2 1\n- 3 2\n+ 2 1 c\n+ 3 2 d\n? 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\nNO\nYES\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个第三种类型的查询$$$k \u003d 3$$$中,我们可以选择一个序列$$$[1, 2, 3]$$$,因为$$$1 \\xrightarrow{\\text{a}} 2 \\xrightarrow{\\text{b}} 3$$$和$$$3 \\xrightarrow{\\text{a}} 2 \\xrightarrow{\\text{b}} 1$$$。\u003c/p\u003e\u003cp\u003e在第二个第三种类型的查询$$$k \u003d 2$$$中,我们找不到序列$$$p_1, p_2$$$,使得弧$$$(p_1, p_2)$$$和$$$(p_2, p_1)$$$具有相同的字符。\u003c/p\u003e\u003cp\u003e在第三个第三种类型的查询中,我们可以选择一个序列$$$[1, 2, 3, 2, 1]$$$,其中$$$1 \\xrightarrow{\\text{a}} 2 \\xrightarrow{\\text{b}} 3 \\xrightarrow{\\text{d}} 2 \\xrightarrow{\\text{c}} 1$$$。\u003c/p\u003e"}}]}