Uneori îmi spun: am să mor  
atât de singuratecă-n mijlocul lor;  
limba simplă a bucuriilor n-am învâțat;  
am să mor ca o pasăre care prea mult a zburat,  
dar n-a făcut cuib nicăieri.

― Oamenii ma uimesc, Magda Isafost
__________________________________________________________

As of writing the informal statement, the winter just came and the statement was in season. Now, it is not winter anymore, so here is the formal statement instead:

You are given a connected graph with N nodes and M edges. You are given Q queries of the following types:
\texttt{1 u}: Given node u (1 ≤ u ≤ N), set the state of the node u to frozen.
\texttt{2 t}: Given t, let t units of time pass by.
\texttt{3 v}: Given node v (1 ≤ v ≤ N), answer if node v is currently frozen.

Initially, no node is frozen.  
The graph has the following property:
If, at time T, a node u is frozen, then, at time (T+1), all neighbours of u become frozen.

For each query of type 3, answer whether the node is currently frozen. 

Note:
If a node is already frozen, it remains unaffected after a type 1 query.
If, for a frozen node u, a neighbour v of node u is frozen at time T, node v remains unaffected at time (T+1).

------ Input Format ------ 

- The first line of input contains three integers N, M, and Q.
- M lines follow, the i^{th} of which contains two integers u_{i} and v_{i}, representing there is an edge between nodes u_{i} and v_{i}.
- Then, Q lines follow, the j^{th} of which contains two integers type_{j} and x_{j}.  
If type_{j} is 1 or 2, it indicates that you must effectuate an update of the type type_{j} with parameter x_{j}. Otherwise, answer the query with parameter x_{j}

------ Output Format ------ 

For each query of type 3, print \texttt{YES} if the queried node is frozen. Otherwise, print \texttt{NO}. 

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{YeS}, \texttt{yEs}, \texttt{yes} and \texttt{YES} will all be treated as identical).

------ Constraints ------ 

$1 ≤N, Q ≤10^{5}$
$1 ≤M ≤3 \cdot 10^{5}$
$1 ≤u_{i}, v_{i} ≤N$
$1 ≤type_{j} ≤3$
$1 ≤x_{j} ≤N$, if the query type is $1$ or $3$.
$1 ≤x_{j} ≤10^{9}$, if the query type is $2$.

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤N ≤1000, 1 ≤Q ≤2000, 1 ≤M ≤3000$.
Subtask 2 (30 points): Each node in the given graph has at most two neighbours.   
Subtask 3 (60 points): Original constraints.

----- Sample Input 1 ------ 
6 6 6
1 2
2 3
4 1
5 4
6 1
6 5
1 1
3 1
1 5
2 1
3 4
3 3
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
Test Case $1$: The graph looks like:

- Query $1$: Freeze the node $1$. The graph looks like:

- Query $2$: Find the status of node $1$. Since node $1$ is frozen, we print $\texttt{YES}$.
- Query $3$: Freeze the node $5$. The graph looks like:

- Query $4$: $1$ unit of time passes. Before this, nodes $1$ and $5$ were frozen.  
After $1$ second, all the neighbours of node $1$, i.e., nodes $2, 4,$ and $6$, and all the neighbours of node $5$, i.e., nodes $4$ and $6$ are frozen.  
Thus, after this query, the frozen nodes in the graph are $1, 2, 4, 5,$ and $6$. The graph looks like:

- Query $5$: Find the status of node $4$. Since node $4$ is frozen, we print $\texttt{YES}$.
- Query $6$: Find the status of node $3$. Since node $3$ is not frozen, we print $\texttt{NO}$.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal


Solutions:
from collections import defaultdict, deque

def solve(n, adj, queries):
	visited = set()
	queue = deque()

	def bfs(time):
		while queue and time > 0:
			size = len(queue)
			for _ in range(size):
				u = queue.popleft()
				for nei in adj[u]:
					if nei in visited:
						continue
					visited.add(nei)
					queue.append(nei)
			time -= 1
	for (t, val) in queries:
		if t == 1:
			if val in visited:
				continue
			visited.add(val)
			queue.append(val)
		elif t == 2:
			bfs(val)
		elif val in visited:
			print('YES')
		else:
			print('NO')
(n, m, q) = list(map(int, input().split()))
adj = defaultdict(set)
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	adj[u].add(v)
	adj[v].add(u)
queries = []
for _ in range(q):
	queries.append(list(map(int, input().split())))
solve(n, adj, queries)


import sys
import os
from math import *
from collections import *
import bisect
from heapq import *
from itertools import permutations
if os.path.exists('input.txt') and os.path.exists('output.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def lcm(a, b):
	k1 = math.gcd(a, b)
	k2 = a * b
	return k2 // k1
mod = 10 ** 9 + 7

def inp():
	return map(int, input().strip().split(' '))

def lis():
	return list(inp())
moD = 998244353
mod = 10 ** 9 + 7
mod = 998244353
mod = 10 ** 9 + 7

def prim(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
ma = 2 * (10 ** 5 + 1)

def update(ind, val, n):
	while ind <= n:
		fenwick[ind] += val
		ind += ind & -ind

def qsum(ind):
	ans = 0
	while ind > 0:
		ans += fenwick[ind]
		ind -= ind & -ind
	return ans

def dfs(adj, vis, u, l):
	vis[u] = 1
	l.add(u)
	for i in adj[u]:
		if vis[i] == 0:
			dfs(adj, vis, i, l)
mod = 10 ** 9 + 7

def dfs(node, p, col, adj, cnt):
	cnt[col] += 1
	for i in adj[node]:
		if i != p:
			dfs(i, node, col ^ 1, adj, cnt)

def solve():
	(n, m, que) = inp()
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = inp()
		adj[u].append(v)
		adj[v].append(u)
	mp = [0 for i in range(n + 1)]
	q = []
	for i in range(que):
		(x, y) = inp()
		if x == 3:
			print('YES' if mp[y] == 1 else 'NO')
		elif x == 1:
			if mp[y] == 0:
				q.append(y)
			mp[y] = 1
		else:
			i = 0
			while i < y and q:
				k = len(q)
				while k > 0:
					if len(q) == 0:
						break
					u = q.pop(0)
					for c in adj[u]:
						if mp[c] == 0:
							mp[c] = 1
							q.append(c)
					k -= 1
				i += 1
t = 1
for _ in range(t):
	solve()


(n, m, q) = map(int, input().split())
l = []
for i in range(n + 1):
	l.append([])
for i in range(m):
	(i, j) = map(int, input().split())
	l[i].append(j)
	l[j].append(i)
queue = []
top = 0
time = 0
isFrozen = [0] * (n + 1)
count = 0
for i in range(q):
	while count < n and len(queue) != top and (time != queue[top][1]):
		vertex = queue[top][0]
		for i in l[vertex]:
			if isFrozen[i]:
				pass
			else:
				isFrozen[i] = 1
				count += 1
				queue.append([i, queue[top][1] + 1])
		top += 1
	(t, v) = map(int, input().split())
	if t == 1:
		isFrozen[v] = 1
		count += 1
		queue.append([v, time])
	if t == 2:
		time += v
	if t == 3:
		if isFrozen[v]:
			print('YES')
		else:
			print('NO')


from sys import stdin
input = stdin.readline

class Graph:

	def __init__(self, n, res):
		self.num = n
		self.data = [[] for _ in range(n)]
		for (x, y) in res:
			self.data[x - 1].append(y - 1)
			self.data[y - 1].append(x - 1)
(n, m, q) = map(int, input().split())
x = []
y = []
for _ in range(m):
	li = input().split()
	x.append(int(li[0]))
	y.append(int(li[1]))
res = list(zip(x, y))
g1 = Graph(n, res)
v = []
a = []
i = 0
j = 0
for _ in range(n):
	v.append(0)
for _ in range(q):
	(b, c) = map(int, input().split())
	if b == 1 and v[c - 1] != 1:
		v[c - 1] = 1
		a.append(c - 1)
		j = j + 1
	if b == 3:
		if v[c - 1] == 1:
			print('YES')
		else:
			print('NO')
	if b == 2:
		if j != n:
			for _ in range(min(c, n - 1)):
				k = 0
				while i <= j - 1:
					s = a[i]
					if j + k == n:
						break
					for t in g1.data[s]:
						if v[t] != 1:
							a.append(t)
							k += 1
							v[t] = 1
							if j + k == n:
								break
					i = i + 1
				j += k
				if i == j or j == n:
					break


from sys import stdin
inp = stdin.readline
(N, M, Q) = map(int, inp().split())
frzn = [False] * (N + 1)
nbr = [[] for nx in range(N + 1)]
for mx in range(M):
	(u, v) = map(int, inp().split())
	nbr[u].append(v)
	nbr[v].append(u)
frnt = []
ans = []
qpend = []
for qx in range(Q):
	(cq, cp) = map(int, inp().split())
	if cq != 3:
		qpend.append((cq, cp))
		continue
	for (q, p) in qpend:
		if q == 1:
			if not frzn[p]:
				frnt.append(p)
				frzn[p] = True
		else:
			while p and frnt:
				newfrnt = []
				for u in frnt:
					for v in nbr[u]:
						if not frzn[v]:
							frzn[v] = True
							newfrnt.append(v)
				frnt = newfrnt
				p -= 1
	ans.append('YES' if frzn[cp] else 'NO')
	qpend = []
print('\n'.join(ans))


from collections import deque, defaultdict

class Graph:

	def __init__(self, n=None):
		self.node_count = n
		self.adj_list = defaultdict(list)

	def add_edge(self, u, v, directed=False):
		if not directed:
			self.adj_list[u].append(v)
			self.adj_list[v].append(u)
		else:
			self.adj_list[u].append(v)

	def bfs(self, q, t, vis):
		for _ in range(t):
			if not q:
				break
			n = len(q)
			for _ in range(n):
				root = q.popleft()
				for x in self.adj_list[root]:
					if not vis[x]:
						vis[x] = 1
						q.append(x)
g = Graph()
(n, m, q) = map(int, input().split())
for _ in range(m):
	(u, v) = map(int, input().split())
	g.add_edge(u, v)
vis = [0] * (n + 1)
queue = deque([])
for _ in range(q):
	(a, b) = map(int, input().split())
	if a == 1:
		if not vis[b]:
			vis[b] = 1
			queue.append(b)
	elif a == 3:
		print('YES') if vis[b] else print('NO')
	elif a == 2:
		g.bfs(queue, b, vis)


import collections

def main():
	(N, M, Q) = map(int, input().split())
	adj_list = collections.defaultdict(list)
	for _ in range(M):
		(u, v) = map(int, input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	frozen = set()
	nbrs_queue = set()

	def bfs_depth(iters: int):
		nonlocal nbrs_queue
		while iters and nbrs_queue:
			nxt_queue = set()
			for node in nbrs_queue:
				if node in frozen:
					continue
				frozen.add(node)
				for nbr in adj_list[node]:
					if nbr not in frozen:
						nxt_queue.add(nbr)
			nbrs_queue = nxt_queue
			iters -= 1
	for _ in range(Q):
		(qtype, node) = map(int, input().split())
		if qtype == 1:
			if node in frozen:
				continue
			frozen.add(node)
			for nbr in adj_list[node]:
				if nbr not in frozen:
					nbrs_queue.add(nbr)
		elif qtype == 2:
			bfs_depth(node)
		elif node in frozen:
			print('YES')
		else:
			print('NO')
main()


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, m, q) = map(int, input().split())
	graph = collections.defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	visited = [0] * (n + 1)
	count = 0
	Q = collections.deque()
	for i in range(q):
		(typ, x) = map(int, input().split())
		if typ == 1:
			if not visited[x]:
				visited[x] = 1
				Q.append(x)
				count += 1
		elif typ == 2:
			time = x
			if count != n:
				while time:
					siz = len(Q)
					for j in range(siz):
						node = Q.popleft()
						l = graph[node]
						for adj in l:
							if not visited[adj]:
								visited[adj] = 1
								count += 1
								if count == n:
									break
								Q.append(adj)
						if count == n:
							break
					if count == n:
						break
					time -= 1
		elif typ == 3:
			if visited[x] == 1:
				print('YES')
			else:
				print('NO')
t = 1
while t != 0:
	solve()
	t -= 1


from collections import defaultdict
adj = defaultdict(list)
(n, m, Q) = map(int, input().split())
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
vis = set()
q = []
for i in range(Q):
	(qt, x) = map(int, input().split())
	if qt == 1:
		if x not in vis:
			q.append(x)
			vis.add(x)
	elif qt == 2:
		while x and q:
			l = len(q)
			while l:
				u = q.pop(0)
				for v in adj[u]:
					if v not in vis:
						q.append(v)
						vis.add(v)
				l -= 1
			x -= 1
	elif x in vis:
		print('YES')
	else:
		print('NO')


from sys import stdin
from collections import deque
inp = stdin.readline
(N, M, Q) = map(int, inp().split())
frzn = [False] * (N + 1)
nbr = [[] for nx in range(N + 1)]
frnt = deque()
ans = []
for mx in range(M):
	(u, v) = map(int, inp().split())
	nbr[u].append(v)
	nbr[v].append(u)
for qx in range(Q):
	(q, p) = map(int, inp().split())
	if q == 1:
		if not frzn[p]:
			frnt.append(p)
			frzn[p] = True
	elif q == 3:
		ans.append('YES' if frzn[p] else 'NO')
	else:
		while p and frnt:
			for _ in range(len(frnt)):
				u = frnt.popleft()
				for v in nbr[u]:
					if not frzn[v]:
						frzn[v] = True
						frnt.append(v)
			p -= 1
print(*ans, sep='\n')


(n, m, q) = map(int, input().split())
graph = dict()
temp = dict()
for i in range(1, n + 1):
	temp[i] = 0
for i in range(m):
	(u, v) = map(int, input().split())
	if u not in graph.keys():
		graph[u] = [v]
		temp[u] = 0
	else:
		graph[u].append(v)
	if v not in graph.keys():
		graph[v] = [u]
		temp[v] = 0
	else:
		graph[v].append(u)
que = list()
for i in range(q):
	(a, b) = map(int, input().split())
	if a == 3:
		if temp[b] == 1:
			print('YES')
		else:
			print('NO')
	elif a == 1:
		if temp[b] == 0:
			que.append(b)
		temp[b] = 1
	else:
		for i in range(b):
			if len(que) == 0:
				break
			length = len(que)
			while length > 0:
				e = que.pop(0)
				length -= 1
				for x in graph[e]:
					if temp[x] == 0:
						temp[x] = 1
						que.append(x)


import heapq
from collections import deque
(n, m, q) = map(int, input().split())
graph = {}
x = 10000000000000
visited = [False for i in range(n + 1)]
vc = n
frozen = deque([])
for i in range(1, n + 1):
	graph[i] = []
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
for _ in range(q):
	(qu, val) = map(int, input().split())
	if qu == 1:
		if not visited[val]:
			vc -= 1
			visited[val] = True
			frozen.append(val)
	elif qu == 2:
		if vc > 0:
			timer = val
			q = frozen
			empty = deque()
			while timer > 0:
				while q:
					vnode = q.popleft()
					for i in graph[vnode]:
						if not visited[i]:
							vc -= 1
							empty.append(i)
							visited[i] = True
					if vc <= 0:
						break
				if vc <= 0:
					break
				q = empty
				empty = deque()
				timer -= 1
			frozen = q
	else:
		print('YES' if visited[val] else 'NO')


(n, m, q) = map(int, input().split())
adj = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
	adj[y].append(x)
freeze = [0] * n
qu = []
t = 0
for i in range(q):
	(x, y) = map(int, input().split())
	if x == 1:
		if not freeze[y - 1]:
			qu.append(y)
		freeze[y - 1] = 1
	elif x == 2:
		while y > 0 and qu:
			ll = len(qu)
			while ll:
				u = qu.pop(0)
				for j in adj[u]:
					if freeze[j - 1] == 0:
						qu.append(j)
					freeze[j - 1] = 1
				ll -= 1
			y -= 1
	elif freeze[y - 1] == 1:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
(n, m, q) = list(map(int, input().split()))
graph = defaultdict(list)
f = [q + 1] * (n + 1)

def bfs(n):
	t = current_time
	queue = list()
	if f[n] > t:
		f[n] = t
		queue.append(n)
	while len(queue) > 0:
		size = len(queue)
		t += 1
		while size > 0:
			o = queue.pop(0)
			for nn in graph[o]:
				if f[nn] > t:
					f[nn] = t
					queue.append(nn)
			size -= 1
while m > 0:
	(u, v) = list(map(int, input().split()))
	graph[u].append(v)
	graph[v].append(u)
	m -= 1
current_time = 0
while q > 0:
	(t, n) = list(map(int, input().split()))
	if t == 1:
		bfs(n)
	elif t == 2:
		current_time += n
	elif f[n] > current_time:
		print('NO')
	else:
		print('YES')
	q -= 1


(n, m, q) = map(int, input().split())
adjancy = dict()
for _ in range(1, n + 1):
	adjancy[_] = []
for _ in range(m):
	(u, v) = map(int, input().split())
	adjancy[u].append(v)
	adjancy[v].append(u)
frozen = set()
visited_neigh = set()
for i in range(q):
	(qu, node) = map(int, input().split())
	if qu == 1:
		frozen.add(node)
	elif qu == 3:
		if node in frozen:
			print('YES')
		else:
			print('NO')
	else:
		length = len(frozen)
		if length == 0 or length == n:
			continue
		tem = frozen.copy()
		for __ in range(node):
			new = set()
			for j in tem:
				if j not in visited_neigh:
					for k in adjancy[j]:
						frozen.add(k)
						new.add(k)
					visited_neigh.add(j)
			tem = new
			new = set()


from collections import defaultdict, deque

def bfs(time):
	cnt = 0
	while que and cnt < time:
		for a in range(len(que)):
			node = que.popleft()
			for neighbour in graph[node]:
				if neighbour not in frozen:
					que.append(neighbour)
					frozen.add(neighbour)
		cnt += 1
graph = defaultdict(list)
(n, m, q) = map(int, input().split())
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
que = deque()
frozen = set()
for i in range(q):
	(code, x) = map(int, input().split())
	if code == 1:
		if x not in frozen:
			que.append(x)
			frozen.add(x)
	elif code == 2:
		bfs(x)
	elif x in frozen:
		print('YES')
	else:
		print('NO')


from collections import deque
frozen = set()
recently_frozen = set()
d = {}
(n, m, q) = map(int, input().split())
for x in range(m):
	(u, v) = map(int, input().split())
	if u not in d:
		d[u] = deque()
	d[u].append(v)
	if v not in d:
		d[v] = deque()
	d[v].append(u)
for x in range(q):
	(type, value) = map(int, input().split())
	if type == 1:
		frozen.add(value)
		recently_frozen.add(value)
	if type == 3:
		if value in frozen:
			print('YES')
		else:
			print('NO')
	if type == 2:
		if len(frozen) == n:
			continue
		while value > 0:
			temp = set()
			for y in recently_frozen:
				for z in d[y]:
					if z not in frozen:
						temp.add(z)
						frozen.add(z)
			recently_frozen = temp
			value -= 1


(n, m, q) = list(map(int, input().split()))
isFrozen = [False] * (n + 1)
chosen = set()
graph = {}
for i in range(1, n + 1):
	graph[i] = []
for _ in range(m):
	(i, j) = list(map(int, input().split()))
	graph[i].append(j)
	graph[j].append(i)
for _ in range(q):
	(type1, val) = list(map(int, input().split()))
	if type1 == 1:
		if isFrozen[val] == False:
			isFrozen[val] = True
			for i in graph[val]:
				if not isFrozen[i]:
					chosen.add(i)
	elif type1 == 3:
		if isFrozen[val]:
			print('YES')
		else:
			print('NO')
	else:
		for i in range(val):
			temp = set()
			if len(chosen) == 0:
				break
			for node in chosen:
				isFrozen[node] = True
				for j in graph[node]:
					if not isFrozen[j]:
						temp.add(j)
			chosen = temp


from collections import deque
(n, m, q) = map(int, input().split())
graph = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
frozen = [False for i in range(n + 1)]
queue = deque()
frozenCount = 0
for _ in range(q):
	(typ, x) = map(int, input().split())
	if typ == 1:
		if frozen[x] == False:
			queue.append(x)
			frozen[x] = True
			frozenCount += 1
	elif typ == 2:
		if frozenCount != n:
			for i in range(x):
				queLen = len(queue)
				for itera in range(queLen):
					node = queue.popleft()
					adjList = graph[node]
					for adj in adjList:
						if frozen[adj] == False:
							frozen[adj] = True
							frozenCount += 1
							if frozenCount == n:
								break
							queue.append(adj)
					if frozenCount == n:
						break
				if frozenCount == n:
					break
	elif typ == 3:
		if frozen[x]:
			print('YES')
		else:
			print('NO')


import copy
(n, m, q1) = map(int, input().split())
adj = []
vis = []
for _ in range(n + 1):
	adj.append([])
	vis.append(0)
for _ in range(m):
	(p, q) = map(int, input().split())
	adj[p].append(q)
	adj[q].append(p)
d = []
for _ in range(q1):
	(type, x) = map(int, input().split())
	if type == 1:
		if vis[x] == 0:
			d.append(x)
		vis[x] = 1
	elif type == 3:
		if vis[x] == 1:
			print('YES')
		else:
			print('NO')
	elif len(d) != 0:
		for _ in range(x):
			k = []
			if len(d) == 0:
				break
			for i in d:
				for j in adj[i]:
					if vis[j] == 0:
						vis[j] = 1
						k.append(j)
			d = copy.deepcopy(k)


def process(n: int, edges: dict, queries: list):
	is_frozen = set()
	frozen_perimeter = set()
	for query in queries:
		qtype = query[0]
		qparam = query[1]
		if qtype == 3:
			if qparam in is_frozen:
				print('YES')
			else:
				print('NO')
		elif qtype == 1:
			if qparam in is_frozen:
				continue
			else:
				is_frozen.add(qparam)
				frozen_perimeter.add(qparam)
		else:
			time = qparam
			while time > 0 and len(frozen_perimeter) > 0:
				next_perimeter = set()
				for node in frozen_perimeter:
					next_perimeter |= edges[node]
				next_perimeter -= is_frozen
				is_frozen |= next_perimeter
				frozen_perimeter = next_perimeter
				time -= 1

def add_directed_edge(edges: dict, edge: list):
	if edge[0] not in edges:
		edges[edge[0]] = set()
	edges[edge[0]].add(edge[1])

def add_undirected_edge(edges: dict, edge: list):
	add_directed_edge(edges, edge)
	add_directed_edge(edges, [edge[1], edge[0]])

def get_list(func):
	return list(map(func, input().split()))

def solve():
	(n, m, q) = get_list(int)
	edges = {}
	for _ in range(m):
		edge = get_list(int)
		add_undirected_edge(edges, edge)
	queries = []
	for _ in range(q):
		queries.append(get_list(int))
	process(n, edges, queries)

def test1():
	n = 6
	edges = {}
	add_undirected_edge(edges, [1, 2])
	add_undirected_edge(edges, [2, 3])
	add_undirected_edge(edges, [4, 1])
	add_undirected_edge(edges, [5, 4])
	add_undirected_edge(edges, [6, 1])
	add_undirected_edge(edges, [6, 5])
	queries = [[1, 1], [3, 1], [1, 5], [2, 1], [3, 4], [3, 3]]
	process(n, edges, queries)
solve()


(n, m, q) = map(int, input().split())
s = [-1 for i in range(n + 1)]
s1 = [[] for i in range(n + 1)]
s2 = []
for i in range(m):
	(u, v) = map(int, input().split())
	s1[u].append(v)
	s1[v].append(u)
for i in range(q):
	(t, j) = map(int, input().split())
	if t == 1:
		if s[j] == -1:
			s[j] = 0
			s2.append(j)
	elif t == 2:
		num = len(s2)
		while j != 0:
			if len(s2) == 0:
				break
			j1 = s2[0]
			s2.pop(0)
			num -= 1
			if s[j1] == 0:
				for k1 in s1[j1]:
					if s[k1] == -1:
						s[k1] = 0
						s2.append(k1)
			if num == 0:
				j -= 1
				num = len(s2)
			s[j1] = 1
	elif t == 3:
		if s[j] == -1:
			print('NO')
		else:
			print('YES')


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
from collections import deque
(n, m, q) = amap()
d = {}
fr = {}
for i in range(1, n + 1):
	d[i] = []
	fr[i] = False
for i in range(m):
	(u, v) = amap()
	d[u].append(v)
	d[v].append(u)
r = deque([])
for i in range(q):
	(t, x) = amap()
	if t == 1:
		if fr.get(x) == False:
			r.append(x)
		fr[x] = True
	elif t == 2:
		r.append(None)
		while r and x:
			curr = r.popleft()
			if curr != None:
				for j in d[curr]:
					if fr.get(j) == False:
						r.append(j)
						fr[j] = True
			else:
				x -= 1
				if r:
					r.append(None)
		if r and r[-1] == None:
			r.pop()
	elif fr.get(x):
		print('YES')
	else:
		print('NO')


def explore(frozen, que, c):
	deq = []
	for i in que:
		for j in adj[i]:
			if frozen[j - 1] == 'NO':
				frozen[j - 1] = 'YES'
				deq.append(j - 1)
				c += 1
	return (frozen, deq, c)
(n, m, q) = map(int, input().split())
adj = [[] for i in range(n)]
for t in range(m):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v)
	adj[v - 1].append(u)
frozen = ['NO' for i in range(n)]
que = []
c = 0
for t in range(q):
	(typ, x) = map(int, input().split())
	if typ == 1:
		if frozen[x - 1] == 'NO':
			frozen[x - 1] = 'YES'
			que.append(x - 1)
			c += 1
	elif typ == 2:
		if c >= n:
			continue
		for k in range(x):
			(frozen, que, c) = explore(frozen, que, c)
	else:
		print(frozen[x - 1])


import math
from collections import Counter, defaultdict, deque
import heapq
import sys
mod = 10 ** 9 + 7
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())

def print(*args, end='\n', sep=' '):
	for i in args:
		sys.stdout.write(str(i))
		sys.stdout.write(sep)
	sys.stdout.write(end)

def make_bfs():
	while q:
		(tt, u) = q[0]
		if tt > spend:
			break
		(tt, u) = heapq.heappop(q)
		if u in frozen:
			continue
		frozen.add(u)
		for v in graph[u]:
			if v not in frozen:
				q.append([tt + 1, v])
(n, m, Q) = intMap()
graph = defaultdict(list)
for i in range(m):
	(u, v) = intMap()
	graph[u].append(v)
	graph[v].append(u)
spend = 0
q = []
frozen = set()
for i in range(Q):
	(tp, v) = intMap()
	if tp == 1:
		heapq.heappush(q, [spend, v])
	if tp == 2:
		spend += v
	if tp == 3:
		make_bfs()
		if v in frozen:
			print('YES')
		else:
			print('NO')


from collections import deque
(n, m, q) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
queue = deque()
frozen = set()

def startFreeze(time):
	minutes = 0
	while queue and minutes < time:
		n = len(queue)
		for _ in range(n):
			u = queue.popleft()
			for v in adj[u]:
				if v not in frozen:
					queue.append(v)
					frozen.add(v)
		minutes += 1
for _ in range(q):
	(qType, x) = map(int, input().split())
	if qType == 1:
		if x - 1 not in frozen:
			queue.append(x - 1)
			frozen.add(x - 1)
	elif qType == 2:
		startFreeze(x)
	elif qType == 3:
		if x - 1 in frozen:
			print('YES')
		else:
			print('NO')


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
Queue = deque()

def solve():
	(n, m, q) = mp()
	d = defaultdict(list)
	for i in range(m):
		(a, b) = mp()
		d[a].append(b)
		d[b].append(a)
	ma = n - 1
	Q = deque()
	v = defaultdict(int)
	for i in range(q):
		(a, b) = mp()
		if a == 3:
			pr('YES' if v[b] else 'NO')
		elif a == 1:
			if v[b] == 0:
				Q.append(b)
				v[b] = 1
		else:
			while Q:
				for j in d[Q[0]]:
					Queue.append(j)
				Q.popleft()
			if ma and Queue:
				while b and ma:
					N = len(Queue)
					for j in range(N):
						if not v[Queue[0]]:
							v[Queue[0]] = 1
							for k in d[Queue[0]]:
								Queue.append(k)
						Queue.popleft()
					ma -= 1
					b -= 1
for _ in range(1):
	solve()


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from queue import PriorityQueue
from queue import Queue
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
import random
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	(n, m, q) = sd()
	gp = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = sd()
		gp[u].append(v)
		gp[v].append(u)
	state = [0] * (n + 1)
	vis = [0] * (n + 1)
	que = []
	for i in range(q):
		(t, u) = sd()
		if t == 1:
			if vis[u] == 0:
				que.append(u)
				vis[u] = 1
				state[u] = 1
			continue
		if t == 3:
			if state[u]:
				print('YES')
				continue
			print('NO')
			continue
		temp = []
		while u > 0 and len(que) > 0:
			u -= 1
			while len(que) > 0:
				ele = que.pop()
				for j in gp[ele]:
					if vis[j] == 1:
						continue
					vis[j] = 1
					state[j] = 1
					temp.append(j)
			que = temp.copy()
			temp = []
for _ in range(1):
	hnbhai(_ + 1)