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.


-----Input-----

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.


-----Output-----

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.


-----Examples-----

Input
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
Output
YES
NO
YES


-----Note-----

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$.

Difficulty: VERY_HARD
Tags: String algorithms

Graph algorithms

Data structures

Constructive algorithms
Skill types: Data structures

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	e = dict()
	same = 0
	diff = 0
	res = []
	for i in range(m):
		a = input().split()
		c = a[0]
		if c == '+':
			u = int(a[1])
			v = int(a[2])
			c = a[3]
			z = e.get((v, u), None)
			if z == c:
				same += 1
			elif z is not None:
				diff += 1
			e[u, v] = c
		elif c == '-':
			u = int(a[1])
			v = int(a[2])
			c = e[u, v]
			del e[u, v]
			z = e.get((v, u), None)
			if z == c:
				same -= 1
			elif z is not None:
				diff -= 1
		else:
			c = int(a[1])
			if c % 2 == 1:
				if diff + same > 0:
					res.append('YES')
				else:
					res.append('NO')
			elif same > 0:
				res.append('YES')
			else:
				res.append('NO')
	print('\n'.join(res))
solve()


(n, m) = map(int, input().split())
(rev, same) = (0, 0)
now = {}
a = [set() for _ in range(n + 1)]
for i in range(m):
	b = input().split()
	x = b[0]
	if x == '+':
		(u, v, w) = (int(b[1]), int(b[2]), b[3])
		a[u].add(v)
		now[u, v] = w
		if (v, u) in now:
			rev += 1
			if now[v, u] == w:
				same += 1
	elif x == '-':
		(u, v) = (int(b[1]), int(b[2]))
		if (v, u) in now:
			rev -= 1
			if now[v, u] == now[u, v]:
				same -= 1
		a[u].remove(v)
		del now[u, v]
	else:
		k = int(b[1])
		if k & 1:
			ans = 'YES' if same or rev else 'NO'
		else:
			ans = 'YES' if same else 'NO'
		print(ans)


import os, sys
from io import BytesIO, IOBase
from collections import defaultdict as dd
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'

def solve():
	(N, M) = getInts()
	graph = [dd(lambda : dd(int)) for _ in range(N)]
	sing_ = 0
	back_ = 0
	for _ in range(M):
		S = getStrs()
		if S[0] == '+':
			(u, v) = [int(s) - 1 for s in S[1:3]]
			c = S[3]
			graph[u][v] = c
			d = graph[v][u]
			if not d:
				d = '0'
			if c == d:
				sing_ += 1
			elif d != '0':
				back_ += 1
		elif S[0] == '-':
			(u, v) = [int(s) - 1 for s in S[1:3]]
			c = graph[u][v]
			d = graph[v][u]
			if not d:
				d = '0'
			if c == d:
				sing_ -= 1
			elif d != '0':
				back_ -= 1
			graph[u][v] = '0'
		else:
			k = int(S[1])
			if k % 2 == 0:
				print('YES' if sing_ > 0 else 'NO')
			else:
				print('YES' if back_ + sing_ > 0 else 'NO')
	return
solve()


import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	(N, M) = getInts()
	graph = [dd(lambda : dd(int)) for _ in range(N)]
	sing_ = 0
	back_ = 0
	base = ord('a') - 1
	for _ in range(M):
		S = getStrs()
		if S[0] == '+':
			(u, v) = [int(s) - 1 for s in S[1:3]]
			c = ord(S[3]) - base
			graph[u][v] = c
			d = graph[v][u]
			if not d:
				d = 0
			if c == d:
				sing_ += 1
			elif d != 0:
				back_ += 1
		elif S[0] == '-':
			(u, v) = [int(s) - 1 for s in S[1:3]]
			c = graph[u][v]
			d = graph[v][u]
			if not d:
				d = 0
			if c == d:
				sing_ -= 1
			elif d != 0:
				back_ -= 1
			graph[u][v] = 0
		else:
			k = int(S[1])
			if k % 2 == 0:
				print('YES' if sing_ > 0 else 'NO')
			else:
				print('YES' if back_ + sing_ > 0 else 'NO')
	return
solve()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
(X, Y) = (0, 0)
D = dict()
for t in range(M):
	S = input().split()
	if S[0] == '?':
		K = int(S[1])
		if K & 1:
			if Y:
				print('YES')
			else:
				print('NO')
		elif X:
			print('YES')
		else:
			print('NO')
	elif S[0] == '+':
		(u, v, c) = (int(S[1]) - 1, int(S[2]) - 1, S[3][0])
		if D.get((v, u), '0') >= 'a':
			Y += 1
		if D.get((v, u), '0') == c:
			X += 1
		D[u, v] = c
	else:
		(u, v) = (int(S[1]) - 1, int(S[2]) - 1)
		if D.get((v, u), '0') >= 'a':
			Y -= 1
		if D.get((v, u), '0') == D[u, v]:
			X -= 1
		D[u, v] = '0'


import sys
from sys import stdin
(n, m) = map(int, stdin.readline().split())
even = 0
odd = 0
arr = [{} for i in range(n)]
ans = []
for i in range(m):
	s = stdin.readline()[:-1]
	if s[0] == '+':
		(ty, u, v, c) = s.split()
		(u, v) = (int(u), int(v))
		u -= 1
		v -= 1
		c = ord(c) - ord('a')
		arr[u][v] = c
		if u in arr[v]:
			if arr[v][u] == c:
				even += 1
			odd += 1
	elif s[0] == '-':
		(ty, u, v) = s.split()
		(u, v) = (int(u), int(v))
		u -= 1
		v -= 1
		c = arr[u][v]
		del arr[u][v]
		if u in arr[v]:
			if arr[v][u] == c:
				even -= 1
			odd -= 1
	else:
		(ty, k) = s.split()
		k = int(k)
		if k % 2 == 0:
			if even > 0:
				ans.append('YES')
			else:
				ans.append('NO')
		elif even == 0 and odd == 0:
			ans.append('NO')
		else:
			ans.append('YES')
print('\n'.join(ans))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = 1
for i in range(t):
	(n, m) = RL()
	g = defaultdict(dict)
	same = edge = 0
	for i in range(m):
		q = input().split()
		if q[0] == '+':
			(u, v, c) = (int(q[1]), int(q[2]), q[3])
			g[u][v] = c
			if u in g[v]:
				if g[v][u] == c:
					same += 1
				edge += 1
		elif q[0] == '-':
			(u, v) = (int(q[1]), int(q[2]))
			if u in g[v]:
				if g[v][u] == g[u][v]:
					same -= 1
				edge -= 1
			del g[u][v]
		else:
			k = int(q[1])
			if k & 1:
				if edge:
					print('YES')
				else:
					print('NO')
			elif same:
				print('YES')
			else:
				print('NO')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
(same, both) = (0, 0)
edges = {}
for _ in range(m):
	x = input().split()
	if x[0] == '+':
		(k, i, j, c) = x
		edges[i, j] = c
		if (j, i) in edges:
			both += 1
			same += edges[j, i] == c
	elif x[0] == '-':
		(k, i, j) = x
		if (j, i) in edges:
			both -= 1
			same -= edges[i, j] == edges[j, i]
		del edges[i, j]
	else:
		i = int(x[1])
		if not i % 2:
			print('YES' if same else 'NO')
		else:
			print('YES' if both else 'NO')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
bothpathnum = 0
equalpathnum = 0
edge = dict()
ans = []
for querynum in range(m):
	inpstr = input()
	if inpstr[0] == '+':
		(u, v, c) = inpstr[2:].split()
		(u, v, c) = (int(u), int(v), ord(c))
		if v * n + u in edge and edge[v * n + u] != 0:
			bothpathnum += 1
			if edge[v * n + u] == c:
				equalpathnum += 1
		edge[u * n + v] = c
	elif inpstr[0] == '-':
		(u, v) = map(int, inpstr[2:].split())
		if v * n + u in edge and edge[v * n + u] != 0:
			bothpathnum -= 1
			if edge[v * n + u] == edge[u * n + v]:
				equalpathnum -= 1
		edge[u * n + v] = 0
	elif inpstr[0] == '?':
		k = int(inpstr[2:])
		if k % 2 == 0:
			if equalpathnum > 0:
				ans.append('YES')
			else:
				ans.append('NO')
		elif bothpathnum > 0:
			ans.append('YES')
		else:
			ans.append('NO')
print(*ans, sep='\n')


import io
import os
import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	double_edges = 0
	same_double_edges = 0
	g = [{} for _ in range(n)]
	for _ in range(m):
		(t, *par) = input().strip().split()
		if t == '+':
			(u, v, c) = par
			u = int(u)
			v = int(v)
			u -= 1
			v -= 1
			if u in g[v]:
				double_edges += 1
				if g[v][u] == c:
					same_double_edges += 1
			g[u][v] = c
		elif t == '-':
			(u, v) = map(int, par)
			u -= 1
			v -= 1
			if u in g[v]:
				double_edges -= 1
				if g[v][u] == g[u][v]:
					same_double_edges -= 1
			del g[u][v]
		else:
			k = int(par[0])
			if k % 2 == 0:
				print('YES' if same_double_edges else 'NO')
			else:
				print('YES' if double_edges else 'NO')
t = 1
for _ in range(t):
	solve()


import io
import os
from collections import defaultdict

def solve(N, queries):
	graph = [defaultdict(int) for i in range(N)]
	same = 0
	edges = 0
	ans = []
	for query in queries:
		if query[0] == '+':
			(_, u, v, c) = query
			u = int(u) - 1
			v = int(v) - 1
			c = ord(c)
			graph[u][v] = c
			if u in graph[v]:
				if graph[v][u] == c:
					same += 1
				edges += 1
		elif query[0] == '-':
			(_, u, v) = query
			u = int(u) - 1
			v = int(v) - 1
			c = graph[u][v]
			if u in graph[v]:
				if graph[v][u] == c:
					same -= 1
				edges -= 1
			del graph[u][v]
		elif query[0] == '?':
			(_, k) = query
			k = int(k)
			if k % 2:
				if edges:
					ans.append('YES')
				else:
					ans.append('NO')
			elif same:
				ans.append('YES')
			else:
				ans.append('NO')
		else:
			assert False
	return '\n'.join(ans)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	queries = (input().decode().rstrip().split() for i in range(M))
	ans = solve(N, queries)
	print(ans)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		inf = float('inf')
		que = []
		d = [inf] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1

class DualSegmentTree:

	def __init__(self, n, segfunc, ide_ele):
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num

	def update(self, l, r, x):
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				self.tree[l] = self.segfunc(self.tree[l], x)
				l += 1
			if r & 1:
				self.tree[r - 1] = self.segfunc(self.tree[r - 1], x)
			l >>= 1
			r >>= 1

	def __getitem__(self, idx):
		idx += self.num
		res = self.ide_ele
		while idx:
			res = self.segfunc(res, self.tree[idx])
			idx >>= 1
		return res

class LazySegmentTree:
	__slots__ = ['merge', 'merge_unit', 'operate', 'merge_operate', 'operate_unit', 'n', 'data', 'lazy']

	def __init__(self, n, init, merge, merge_unit, operate, merge_operate, operate_unit):
		self.merge = merge
		self.merge_unit = merge_unit
		self.operate = operate
		self.merge_operate = merge_operate
		self.operate_unit = operate_unit
		self.n = (n - 1).bit_length()
		self.data = [merge_unit for i in range(1 << self.n + 1)]
		self.lazy = [operate_unit for i in range(1 << self.n + 1)]
		if init:
			for i in range(n):
				self.data[2 ** self.n + i] = init[i]
			for i in range(2 ** self.n - 1, 0, -1):
				self.data[i] = self.merge(self.data[2 * i], self.data[2 * i + 1])

	def propagate(self, v):
		ope = self.lazy[v]
		if ope == self.operate_unit:
			return
		self.lazy[v] = self.operate_unit
		self.data[v << 1] = self.operate(self.data[v << 1], ope)
		self.data[(v << 1) + 1] = self.operate(self.data[(v << 1) + 1], ope)
		self.lazy[v << 1] = self.merge_operate(self.lazy[v << 1], ope)
		self.lazy[(v << 1) + 1] = self.merge_operate(self.lazy[(v << 1) + 1], ope)

	def propagate_above(self, i):
		m = i.bit_length() - 1
		for bit in range(m, 0, -1):
			v = i >> bit
			self.propagate(v)

	def remerge_above(self, i):
		while i:
			c = self.merge(self.data[i], self.data[i ^ 1])
			i >>= 1
			self.data[i] = self.operate(c, self.lazy[i])

	def update(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		while l < r:
			if l & 1:
				self.data[l] = self.operate(self.data[l], x)
				self.lazy[l] = self.merge_operate(self.lazy[l], x)
				l += 1
			if r & 1:
				self.data[r - 1] = self.operate(self.data[r - 1], x)
				self.lazy[r - 1] = self.merge_operate(self.lazy[r - 1], x)
			l >>= 1
			r >>= 1
		self.remerge_above(l0)
		self.remerge_above(r0)

	def query(self, l, r):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		res = self.merge_unit
		while l < r:
			if l & 1:
				res = self.merge(res, self.data[l])
				l += 1
			if r & 1:
				res = self.merge(res, self.data[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.data[l][0] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.data[r - 1][0] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		res = -1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			res = pos - self.num
		if Rmin != -1:
			pos = Rmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			if res == -1:
				res = pos - self.num
			else:
				res = min(res, pos - self.num)
		return res

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

def _inv_gcd(a, b):
	a %= b
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		(s, t) = (t, s)
		(m0, m1) = (m1, m0)
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def crt(r, m):
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = r[i] % m[i]
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = _inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(n, m) = mi()
dic = {}
odd = 0
even = 0
for _ in range(m):
	query = input().split()
	if len(query) == 2:
		k = int(query[1])
		if k % 2 and odd:
			print('YES')
		elif not k % 2 and even:
			print('YES')
		else:
			print('NO')
	else:
		(u, v) = map(int, query[1:3])
		if query[0] == '+':
			if (min(u, v), max(u, v)) not in dic:
				dic[min(u, v), max(u, v)] = [None, None]
			dic[min(u, v), max(u, v)][int(u < v)] = query[-1]
			(U, V) = (min(u, v), max(u, v))
			if dic[U, V][0] and dic[U, V][1]:
				odd += 1
			if dic[U, V][0] and dic[U, V][1] and (dic[U, V][0] == dic[U, V][1]):
				even += 1
		else:
			(U, V) = (min(u, v), max(u, v))
			if dic[U, V][0] and dic[U, V][1]:
				odd -= 1
			if dic[U, V][0] and dic[U, V][1] and (dic[U, V][0] == dic[U, V][1]):
				even -= 1
			dic[min(u, v), max(u, v)][int(u < v)] = None


import sys
(n, m) = map(int, sys.stdin.readline().split())
D = {}
edges2 = set()
edges1 = set()
for i in range(m):
	(s, *A) = sys.stdin.readline().split()
	if s == '+':
		(u, v, c) = (int(A[0]), int(A[1]), A[2])
		D[u, v] = c
		if (v, u) in D and D[v, u] == c:
			edges2.add(tuple(sorted((u, v))))
			if tuple(sorted((u, v))) in edges1:
				edges1.remove(tuple(sorted((u, v))))
		elif (v, u) in D:
			edges1.add(tuple(sorted((u, v))))
			if tuple(sorted((u, v))) in edges2:
				edges2.remove(tuple(sorted((u, v))))
	if s == '-':
		(u, v) = (int(A[0]), int(A[1]))
		D.pop((u, v), None)
		if tuple(sorted((u, v))) in edges1:
			edges1.remove(tuple(sorted((u, v))))
		if tuple(sorted((u, v))) in edges2:
			edges2.remove(tuple(sorted((u, v))))
	if s == '?':
		k = int(A[0])
		if k % 2 == 0:
			sys.stdout.write('YES' if edges2 else 'NO')
		else:
			sys.stdout.write('YES' if edges1 or edges2 else 'NO')
		sys.stdout.write('\n')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
graph = []
for i in range(n):
	graph.append({})
numcyc = 0
numgoodcyc = 0
for i in range(m):
	s = list(map(str, input().split()))
	if s[0] == '+':
		x = int(s[1]) - 1
		y = int(s[2]) - 1
		c = s[3]
		graph[x][y] = c
		if x in graph[y] and graph[y][x] != 0:
			numcyc += 1
			if graph[y][x] == c:
				numgoodcyc += 1
	elif s[0] == '-':
		x = int(s[1]) - 1
		y = int(s[2]) - 1
		if y in graph[x] and x in graph[y] and (graph[x][y] != 0) and (graph[y][x] != 0):
			numcyc -= 1
			if graph[x][y] == graph[y][x]:
				numgoodcyc -= 1
		graph[x][y] = 0
	else:
		k = int(s[1])
		if k % 2 == 0:
			if numgoodcyc > 0:
				print('YES')
			else:
				print('NO')
		elif numcyc > 0:
			print('YES')
		else:
			print('NO')