A-Z Graph

题意翻译

给定一个**有向图**，每一条边上有一个小写字母，初始该图为空。 有 $m$ 次操作，格式如下： - `+ u v c` 添加一条从 $u$ 到 $v$ 的有向边，上面的字母为 $c$ ，保证在此时不存在 $u$ 到 $v$ 的有向边 - `- u v` 删除 $u$ 到 $v$ 的有向边，保证此时存在 $u$ 到 $v$ 的有向边 - `? k` 询问是否可以构造出一个长度为 $k$ 的序列 $v_1,v_2,\cdots,v_k$ ，满足同时存在一条 $v_1\rightarrow v_2\rightarrow \cdots \rightarrow v_k$ 和一条 $v_k\rightarrow v_{k-1}\rightarrow \cdots \rightarrow v_1$ 的路径，且顺次写下两条路径上经过的边的字母，得到的两个长度为 $k-1$ 的字符串是相同的。你**可以**重复经过一个点多次。 $2\le n\le 2\cdot 10^5\ ,\ 1\le m\le 2\cdot 10^5$ 对于操作 `+` ，满足 $1\le u,v\le n\ ,\ u\neq v$ ，$c$ 是一个小写字母 对于操作 `-` ，满足 $1\le u,v\le n\ ,\ u\neq v$ 对于操作 `?` ，满足 $2\le k\le 10^5$

题目描述

You are given a directed graph consisting of $ n $ vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty. You should process $ m $ queries with it. Each query is one of three types: - " $ + $ $ u $ $ v $ $ c $ " — add arc from $ u $ to $ v $ with label $ c $ . It's guaranteed that there is no arc $ (u, v) $ in the graph at this moment; - " $ - $ $ u $ $ v $ " — erase arc from $ u $ to $ v $ . It's guaranteed that the graph contains arc $ (u, v) $ at this moment; - " $ ? $ $ k $ " — 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'll get the same string. You can visit the same vertices any number of times.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of vertices in the graph and the number of queries. The next $ m $ lines contain queries — one per line. Each query is one of three types: - " $ + $ $ u $ $ v $ $ c $ " ( $ 1 \le u, v \le n $ ; $ u \neq v $ ; $ c $ is a lowercase Latin letter); - " $ - $ $ u $ $ v $ " ( $ 1 \le u, v \le n $ ; $ u \neq v $ ); - " $ ? $ $ k $ " ( $ 2 \le k \le 10^5 $ ). It's guaranteed that you don't add multiple edges and erase only existing edges. Also, there is at least one query of the third type.

输出格式

For each query of the third type, print YES if there exist the sequence $ v_1, v_2, \dots, v_k $ described above, or NO otherwise.

输入输出样例

输入样例 #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

说明

In the first query of the third type $ k = 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 $ . In the second query of the third type $ k = 2 $ , and we can't find sequence $ p_1, p_2 $ such that arcs $ (p_1, p_2) $ and $ (p_2, p_1) $ have the same characters. In 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 $ .