{"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\u003eYou are given a directed graph consisting of $$$n$$$ vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty.\u003c/p\u003e\u003cp\u003eYou should process $$$m$$$ queries with it. Each query is one of three types: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$\u003c/span\u003e\"\u0026nbsp;— add arc from $$$u$$$ to $$$v$$$ with label $$$c$$$. It\u0027s guaranteed that there is no arc $$$(u, v)$$$ in the graph at this moment; \u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$-$$$ $$$u$$$ $$$v$$$\u003c/span\u003e\"\u0026nbsp;— erase arc from $$$u$$$ to $$$v$$$. It\u0027s guaranteed that the graph contains arc $$$(u, v)$$$ at this moment; \u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e$$$?$$$ $$$k$$$\u003c/span\u003e\"\u0026nbsp;— 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\u0027ll get the same string. You can visit the same vertices any number of times. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \\le n \\le 2 \\cdot 10^5$$$; $$$1 \\le m \\le 2 \\cdot 10^5$$$)\u0026nbsp;— the number of vertices in the graph and the number of queries.\u003c/p\u003e\u003cp\u003eThe next $$$m$$$ lines contain queries\u0026nbsp;— one per line. Each query is one of three types: \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$$$ is a lowercase Latin letter); \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\u003eIt\u0027s guaranteed that you don\u0027t add multiple edges and erase only existing edges. Also, there is at least one query of the third type.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query of the third type, print \u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e if there exist the sequence $$$v_1, v_2, \\dots, v_k$$$ described above, or \u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e otherwise.\u003c/p\u003e"}},{"title":"Examples","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\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first query of the third type $$$k \u003d 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$$$.\u003c/p\u003e\u003cp\u003eIn the second query of the third type $$$k \u003d 2$$$, and we can\u0027t find sequence $$$p_1, p_2$$$ such that arcs $$$(p_1, p_2)$$$ and $$$(p_2, p_1)$$$ have the same characters.\u003c/p\u003e\u003cp\u003eIn 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$$$.\u003c/p\u003e"}}]}