When you play the game of thrones, you win, or you die. There is no middle ground.

Cersei Lannister, A Game of Thrones by George R. R. Martin

There are $n$ nobles, numbered from $1$ to $n$. Noble $i$ has a power of $i$. There are also $m$ "friendships". A friendship between nobles $a$ and $b$ is always mutual.

A noble is defined to be vulnerable if both of the following conditions are satisfied:

the noble has at least one friend, and

all of that noble's friends have a higher power.

You will have to process the following three types of queries.

Add a friendship between nobles $u$ and $v$.

Remove a friendship between nobles $u$ and $v$.

Calculate the answer to the following process.

The process: all vulnerable nobles are simultaneously killed, and all their friendships end. Then, it is possible that new nobles become vulnerable. The process repeats itself until no nobles are vulnerable. It can be proven that the process will end in finite time. After the process is complete, you need to calculate the number of remaining nobles.

Note that the results of the process are not carried over between queries, that is, every process starts with all nobles being alive!


-----Input-----

The first line contains the integers $n$ and $m$ ($1 \le n \le 2\cdot 10^5$, $0 \le m \le 2\cdot 10^5$) — the number of nobles and number of original friendships respectively.

The next $m$ lines each contain the integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$), describing a friendship. No friendship is listed twice.

The next line contains the integer $q$ ($1 \le q \le 2\cdot {10}^{5}$) — the number of queries.

The next $q$ lines contain the queries themselves, each query has one of the following three formats.

$1$ $u$ $v$ ($1 \le u,v \le n$, $u \ne v$) — add a friendship between $u$ and $v$. It is guaranteed that $u$ and $v$ are not friends at this moment.

$2$ $u$ $v$ ($1 \le u,v \le n$, $u \ne v$) — remove a friendship between $u$ and $v$. It is guaranteed that $u$ and $v$ are friends at this moment.

$3$ — print the answer to the process described in the statement.


-----Output-----

For each type $3$ query print one integer to a new line. It is guaranteed that there will be at least one type $3$ query.


-----Examples-----

Input
4 3
2 1
1 3
3 4
4
3
1 2 3
2 3 1
3
Output
2
1
Input
4 3
2 3
3 4
4 1
1
3
Output
1


-----Note-----

Consider the first example. In the first type 3 query, we have the diagram below.

In the first round of the process, noble $1$ is weaker than all of his friends ($2$ and $3$), and is thus killed. No other noble is vulnerable in round 1. In round 2, noble $3$ is weaker than his only friend, noble $4$, and is therefore killed. At this point, the process ends, and the answer is $2$.

In the second type 3 query, the only surviving noble is $4$.

The second example consists of only one type $3$ query. In the first round, two nobles are killed, and in the second round, one noble is killed. The final answer is $1$, since only one noble survives.

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search

Graph algorithms

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
l = [0] * (n + 1)
for i in range(m):
	(u, v) = sorted(map(int, input().split()))
	l[u] += 1
c = 0
for i in range(1, n + 1):
	if l[i] == 0:
		c += 1
z = []
q = int(input())
for i in range(q):
	s = input().split()
	if s[0] == '1':
		(u, v) = sorted(map(int, s[1:]))
		l[u] += 1
		if l[u] == 1:
			c -= 1
	if s[0] == '2':
		(u, v) = sorted(map(int, s[1:]))
		l[u] -= 1
		if l[u] == 0:
			c += 1
	if s[0] == '3':
		z.append(str(c))
print('\n'.join(z))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
E = [0] * n
ans = n
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	if u > v:
		(u, v) = (v, u)
	E[u] += 1
	if E[u] == 1:
		ans -= 1
q = int(input())
for i in range(q):
	tmp = input()
	if len(tmp) > 3:
		(d, u, v) = map(int, tmp.split())
		u -= 1
		v -= 1
		if u > v:
			(u, v) = (v, u)
		if d == 1:
			E[u] += 1
			if E[u] == 1:
				ans -= 1
		else:
			E[u] -= 1
			if E[u] == 0:
				ans += 1
	else:
		print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
friends = [0] * n
dead = 0
for _ in range(m):
	(i, j) = map(int, input().split())
	if friends[min(i, j)] == 0:
		dead += 1
	friends[min(i, j)] += 1
q = int(input())
for _ in range(q):
	a = input().split()
	if a[0] == '1':
		(i, j) = (int(a[1]), int(a[2]))
		if friends[min(i, j)] == 0:
			dead += 1
		friends[min(i, j)] += 1
	if a[0] == '2':
		(i, j) = (int(a[1]), int(a[2]))
		if friends[min(i, j)] == 1:
			dead -= 1
		friends[min(i, j)] -= 1
	if a[0] == '3':
		print(n - dead)


N = 200010
f = [-1] * N

def find(x):
	if f[x] == x:
		return x
	f[x] = find(f[x])
	return f[x]

def ufsInit():
	for i in range(1, n + 1):
		f[i] = i
a = [0] * N
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
for i in range(0, m):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	a[x] += 1
cnt = 0
for i in range(1, n + 1):
	cnt += a[i] == 0
q = int(input())
for i in range(0, q):
	l = list(map(int, input().split()))
	if l[0] == 3:
		print(cnt)
		continue
	(x, y) = (l[1], l[2])
	if x > y:
		(x, y) = (y, x)
	if l[0] == 1:
		a[x] += 1
		if a[x] == 1:
			cnt -= 1
	elif l[0] == 2:
		a[x] -= 1
		if a[x] == 0:
			cnt += 1


import sys
input = sys.stdin.readline
(n, q) = list(map(int, input().split()))
arr = [0] * n
c = 0
for _ in range(q):
	(a, b) = map(int, input().split())
	if a < b:
		ind = a - 1
	else:
		ind = b - 1
	arr[ind] += 1
	if arr[ind] == 1:
		c += 1
for i in range(int(input())):
	y = list(map(int, input().split()))
	if len(y) == 1:
		print(n - c)
		continue
	(v, a, b) = y
	if a < b:
		ind = a - 1
	else:
		ind = b - 1
	if v == 1:
		arr[ind] += 1
		if arr[ind] == 1:
			c += 1
	elif v == 2:
		arr[ind] -= 1
		if arr[ind] == 0:
			c -= 1


import sys
input = sys.stdin.readline
cnt = [0] * 200050
ans = 0
(n, m) = map(int, input().split())
for i in range(1, m + 1):
	(u, v) = map(int, input().split())
	if u > v:
		(u, v) = (v, u)
	cnt[u] += 1
	if cnt[u] == 1:
		ans += 1
q = int(input().strip())
while q:
	query = list(map(int, input().split()))
	if query[0] == 1:
		(u, v) = (query[1], query[2])
		if u > v:
			(u, v) = (v, u)
		cnt[u] += 1
		if cnt[u] == 1:
			ans += 1
	elif query[0] == 2:
		(u, v) = (query[1], query[2])
		if u > v:
			(u, v) = (v, u)
		cnt[u] -= 1
		if cnt[u] == 0:
			ans -= 1
	else:
		print(n - ans)
	q -= 1


import sys

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

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline()

def out(x):
	return sys.stdout.write(str(x))
(n, q) = list(map(int, input().split()))
arr = [0] * n
c = 0
for _ in range(q):
	(a, b) = map(int, input().split())
	if a < b:
		ind = a - 1
	else:
		ind = b - 1
	arr[ind] += 1
	if arr[ind] == 1:
		c += 1
for i in range(int(input())):
	y = list(map(int, input().split()))
	if len(y) == 1:
		print(n - c)
		continue
	(v, a, b) = y
	if a < b:
		ind = a - 1
	else:
		ind = b - 1
	if v == 1:
		arr[ind] += 1
		if arr[ind] == 1:
			c += 1
	elif v == 2:
		arr[ind] -= 1
		if arr[ind] == 0:
			c -= 1


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [0] * (n + 1)
for _ in range(m):
	(x, y) = map(int, input().split())
	y = min(x, y)
	a[y] += 1
summ = 0
for i in range(1, n + 1):
	if a[i] == 0:
		summ += 1
q = int(input())
for _ in range(q):
	x = list(map(int, input().split()))
	if x[0] == 3:
		print(summ)
	elif x[0] == 1:
		v = min(x[1], x[2])
		if a[v] == 0:
			summ -= 1
		a[v] += 1
	elif x[0] == 2:
		v = min(x[1], x[2])
		a[v] -= 1
		if a[v] == 0:
			summ += 1


import sys

def add(d, obj, counter):
	if d[obj] == 0:
		counter += 1
	d[obj] += 1
	return counter

def sub(d, obj, counter):
	d[obj] -= 1
	if d[obj] == 0:
		counter -= 1
	return counter
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = {x: 0 for x in range(1, n + 1)}
count = 0
for i in range(m):
	b = [int(x) for x in input().split()]
	count = add(a, min(b), count)
q = int(input())
for i in range(q):
	c = [int(x) for x in input().split()]
	if c[0] == 1:
		count = add(a, min(c[1:]), count)
	elif c[0] == 2:
		count = sub(a, min(c[1:]), count)
	elif c[0] == 3:
		print(n - count)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
data = [0 for i in range(n + 1)]
ans = n
while m > 0:
	(a, b) = list(map(int, input().split()))
	if a > b:
		(a, b) = (b, a)
	if data[a] == 0:
		ans -= 1
	data[a] += 1
	m -= 1
q = int(input())
while q > 0:
	q -= 1
	item = list(map(int, input().split()))
	if len(item) == 1:
		print(ans)
	elif item[0] == 1:
		(a, b) = item[1:]
		if a > b:
			(a, b) = (b, a)
		if data[a] == 0:
			ans -= 1
		data[a] += 1
	elif item[0] == 2:
		(a, b) = item[1:]
		if a > b:
			(a, b) = (b, a)
		data[a] -= 1
		if data[a] == 0:
			ans += 1


import sys
input = sys.stdin.readline
(nn, m) = map(int, input().split())
n = nn
b = [0 for i in range(n + 1)]
p = 0
for i in range(m):
	(c, d) = map(int, input().split())
	f = min(c, d)
	if b[f] == 0:
		p += 1
	b[f] += 1
q = int(input())
for i in range(q):
	(a, *bb) = map(int, input().split())
	if a == 1:
		d = min(bb)
		if b[d] == 0:
			p += 1
		b[d] += 1
	elif a == 2:
		d = min(bb)
		b[d] -= 1
		if b[d] == 0:
			p -= 1
	else:
		print(n - p)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = map(int, sys.stdin.readline().rstrip().split())
a = [0] * (n + 1)
for x in range(m):
	(u, v) = map(int, sys.stdin.readline().rstrip().split())
	if u < v:
		a[u] += 1
	else:
		a[v] += 1
c = 0
for x in range(1, n + 1):
	if a[x] == 0:
		c += 1
test = int(sys.stdin.readline().rstrip())
while test > 0:
	test -= 1
	q = list(map(int, sys.stdin.readline().rstrip().split()))
	if len(q) == 1:
		print(c)
	elif q[0] == 1:
		if q[1] < q[2]:
			a[q[1]] += 1
			if a[q[1]] == 1:
				c -= 1
		else:
			a[q[2]] += 1
			if a[q[2]] == 1:
				c -= 1
	elif q[1] < q[2]:
		a[q[1]] -= 1
		if a[q[1]] == 0:
			c += 1
	else:
		a[q[2]] -= 1
		if a[q[2]] == 0:
			c += 1


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = [-1] + [0] * n
ct = 0
for x in range(m):
	(a, b) = map(int, input().split())
	if a < b:
		c = a
	else:
		c = b
	arr[c] += 1
	if arr[c] == 1:
		ct += 1
for y in range(int(input())):
	lst = list(map(int, input().split()))
	if lst[0] == 3:
		print(n - ct)
		continue
	(op, a, b) = lst
	if a < b:
		c = a
	else:
		c = b
	if op == 1:
		arr[c] += 1
		if arr[c] == 1:
			ct += 1
	elif op == 2:
		arr[c] -= 1
		if arr[c] == 0:
			ct -= 1


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
x = [0] * (n + 1)
c = 0
for i in range(m):
	(u, v) = map(int, input().split())
	mn = min(u, v)
	if x[mn] == 0:
		c += 1
	x[mn] += 1
q = int(input())
for i in range(q):
	(a, *b) = map(int, input().split())
	if a == 3:
		print(n - c)
	elif a == 1:
		d = min(b)
		if x[d] == 0:
			c += 1
		x[d] += 1
	else:
		d = min(b)
		x[d] -= 1
		if x[d] == 0:
			c -= 1


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = [0] * n
ans = n
for x in range(m):
	(u, v) = map(int, input().split())
	k = min(u, v)
	if arr[k - 1] == 0:
		ans -= 1
	arr[k - 1] += 1
for tt in range(int(input())):
	l = list(map(int, input().split()))
	a = l[0]
	if a == 1:
		(u, v) = (l[1], l[2])
		k = min(u, v)
		if arr[k - 1] == 0:
			ans -= 1
		arr[k - 1] += 1
	elif a == 2:
		(u, v) = (l[1], l[2])
		k = min(u, v)
		arr[k - 1] -= 1
		if arr[k - 1] == 0:
			ans += 1
	else:
		print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
count = [0] * (n + 1)
preans = n
for i in range(m):
	arr = list(map(int, input().split()))
	mini = min(arr)
	if count[mini] == 0:
		count[mini] += 1
		preans -= 1
	else:
		count[mini] += 1
ans = preans
temp = count
for i in range(int(input())):
	q = list(map(int, input().split()))
	if len(q) == 1:
		print(ans)
	elif q[0] == 1:
		mini = min(q[1:])
		if temp[mini] == 0:
			ans -= 1
			temp[mini] += 1
		else:
			temp[mini] += 1
	else:
		mini = min(q[1:])
		if temp[mini] == 1:
			ans += 1
			temp[mini] -= 1
		else:
			temp[mini] -= 1


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
li = [0] * (n + 1)
for i in range(m):
	(u, v) = map(int, stdin.readline().split())
	li[min(u, v)] += 1
a = 0
for j in range(1, n + 1):
	if li[j] == 0:
		a = a + 1
q = int(stdin.readline())
for j in range(q):
	ai = list(map(int, stdin.readline().split()))
	if ai[0] == 3:
		print(a)
	elif ai[0] == 2:
		li[min(ai[1], ai[2])] -= 1
		if li[min(ai[1], ai[2])] == 0:
			a = a + 1
	else:
		li[min(ai[1], ai[2])] += 1
		if li[min(ai[1], ai[2])] == 1:
			a = a - 1


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
a = [0] * (n + 1)
ans = n
for i in range(m):
	(u, v) = list(map(int, input().split()))
	u = min(u, v)
	if a[u] == 0:
		ans -= 1
	a[u] += 1
q = int(input())
for i in range(q):
	b = list(map(int, input().split()))
	if b[0] == 1:
		b[1] = min(b[1], b[2])
		if a[b[1]] == 0:
			ans -= 1
		a[b[1]] += 1
	elif b[0] == 2:
		b[1] = min(b[1], b[2])
		a[b[1]] -= 1
		if a[b[1]] == 0:
			ans += 1
	else:
		print(ans)


from sys import stdin
(N, M) = map(int, stdin.readline().split())
counts = [0] * (N + 1)
ans = 0
for _ in range(M):
	(u, v) = map(int, stdin.readline().split())
	if u > v:
		(u, v) = (v, u)
	counts[u] += 1
	if counts[u] == 1:
		ans += 1
Q = int(stdin.readline())
for _ in range(Q):
	args = list(map(int, stdin.readline().split()))
	if args[0] == 1:
		(u, v) = (args[1], args[2])
		if u > v:
			(u, v) = (v, u)
		counts[u] += 1
		if counts[u] == 1:
			ans += 1
	elif args[0] == 2:
		(u, v) = (args[1], args[2])
		if u > v:
			(u, v) = (v, u)
		counts[u] -= 1
		if counts[u] == 0:
			ans -= 1
	else:
		print(N - ans)


import sys
from collections import defaultdict
(n, m) = map(int, sys.stdin.readline().strip().split())
nobles = defaultdict(set)
unvul_num = defaultdict(int)

def get_key(u, v):
	(u, v) = (u, v) if u < v else (v, u)
	return (u, v)

def add(u, v):
	(u, v) = get_key(u, v)
	unvul_num[u] += 1

def delete(u, v):
	(u, v) = get_key(u, v)
	unvul_num[u] -= 1
	if unvul_num[u] == 0:
		unvul_num.pop(u)

def process(unvul_num):
	print(n - len(unvul_num))
for _ in range(m):
	line = sys.stdin.readline()
	(u, v) = map(int, line.strip().split())
	add(u, v)
q = int(sys.stdin.readline().strip())
for _ in range(q):
	cmd = sys.stdin.readline().strip()
	if cmd.startswith('1'):
		(u, v) = map(int, cmd[1:].strip().split())
		add(u, v)
	elif cmd.startswith('2'):
		(u, v) = map(int, cmd[1:].strip().split())
		delete(u, v)
	else:
		assert cmd == '3'
		process(unvul_num)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = map(int, sys.stdin.readline().rstrip().split())
l = [0] * (n + 1)
for _ in range(m):
	(u, v) = sorted(map(int, sys.stdin.readline().rstrip().split()))
	l[u] += 1
c = 0
for i in range(1, n + 1):
	if l[i] == 0:
		c += 1
for _ in range(int(sys.stdin.readline().rstrip())):
	a = list(map(int, sys.stdin.readline().rstrip().split()))
	if a[0] == 1:
		u = min(a[1], a[2])
		l[u] += 1
		if l[u] == 1:
			c -= 1
	elif a[0] == 2:
		u = min(a[1], a[2])
		l[u] -= 1
		if l[u] == 0:
			c += 1
	else:
		print(c)


from sys import stdin
input = stdin.readline
(m, n) = map(int, input().split())
dp = [0] * (m + 1)
dead = 0
for i in range(n):
	(u, v) = map(int, input().split())
	if dp[min(u, v)] == 0:
		dead += 1
	dp[min(u, v)] += 1
for q in range(int(input())):
	command = list(input().split())
	if command[0] == '1':
		if dp[min(int(command[1]), int(command[2]))] == 0:
			dead += 1
		dp[min(int(command[1]), int(command[2]))] += 1
	elif command[0] == '2':
		dp[min(int(command[1]), int(command[2]))] -= 1
		if dp[min(int(command[1]), int(command[2]))] == 0:
			dead -= 1
	elif command[0] == '3':
		print(m - dead)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
num = [1] * n
cnt2 = [0] * n
for i in range(m):
	(a, b) = map(int, input().split())
	num[min(a, b) - 1] = 0
	cnt2[min(a, b) - 1] += 1
q = int(input())
cnt = num.count(1)
for i in range(q):
	que = list(map(int, input().split()))
	if que[0] == 1:
		if cnt2[min(que[1], que[2]) - 1] == 0:
			cnt -= 1
		cnt2[min(que[1], que[2]) - 1] += 1
	elif que[0] == 2:
		if cnt2[min(que[1], que[2]) - 1] == 1:
			cnt += 1
		cnt2[min(que[1], que[2]) - 1] -= 1
	else:
		print(cnt)


from math import *
from collections import defaultdict as dt
from sys import stdin
inp = lambda : stdin.readline().strip()
I = lambda : int(inp())
M = lambda : map(int, inp().split())
L = lambda : list(M())
mod = 1000000007
inf = 100000000000000000000
ss = 'abcdefghijklmnopqrstuvwxyz'

def solve():
	(n, m) = M()
	d = dt(int)
	c = 0
	for i in range(m):
		(u, v) = M()
		d[min(u, v)] += 1
		if d[min(u, v)] == 1:
			c = c + 1
	for i in range(I()):
		q = L()
		if q[0] == 1:
			d[min(q[1], q[2])] += 1
			if d[min(q[1], q[2])] == 1:
				c = c + 1
		elif q[0] == 2:
			d[min(q[1], q[2])] -= 1
			if d[min(q[1], q[2])] == 0:
				c = c - 1
		else:
			print(n - c)
tt = 1
for _ in range(tt):
	solve()


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inlt()
a = []
m = n[1]
n = n[0]
ans = n
for i in range(0, n + 1):
	a.append(0)
for i in range(0, m):
	x = inlt()
	y = x[1]
	x = x[0]
	a[min(x, y)] -= 1
for i in range(1, n + 1):
	if a[i] < 0:
		ans -= 1
q = inp()
for i in range(0, q):
	q1 = inlt()
	if q1[0] == 1:
		j = q1[1]
		k = q1[2]
		if a[min(j, k)] == 0:
			ans -= 1
		a[min(j, k)] -= 1
	elif q1[0] == 2:
		j = q1[1]
		k = q1[2]
		a[min(j, k)] += 1
		if a[min(j, k)] == 0:
			ans += 1
	else:
		print(ans)


import sys
input = sys.stdin.readline
t = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	can = 0
	dead = 0
	now = [[0, 0] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		if a > b:
			now[a][0] += 1
			now[b][1] += 1
		else:
			now[b][0] += 1
			now[a][1] += 1
	ans = 0
	for i in range(1, n + 1):
		if now[i][1] == 0:
			ans += 1
	q = int(input())
	for i in range(q):
		inp = list(map(int, input().split()))
		if len(inp) == 1:
			print(ans)
			continue
		if inp[0] == 1:
			(a, b) = (inp[1], inp[2])
			if a > b:
				if now[b][1] == 0:
					ans -= 1
				now[a][0] += 1
				now[b][1] += 1
			else:
				if now[a][1] == 0:
					ans -= 1
				now[b][0] += 1
				now[a][1] += 1
		else:
			(a, b) = (inp[1], inp[2])
			if a > b:
				if now[b][1] == 1:
					ans += 1
				now[a][0] -= 1
				now[b][1] -= 1
			else:
				if now[a][1] == 1:
					ans += 1
				now[b][0] -= 1
				now[a][1] -= 1


import sys
input_file = sys.stdin
output_file = sys.stdout
(n_str, m_str) = input_file.readline().strip().split()
n = int(n_str)
m = int(m_str)
f = [0] * (n + 1)
for i in range(m):
	(u, v) = input_file.readline().strip().split()
	(a, b) = (min(int(u), int(v)), max(int(u), int(v)))
	f[a] += 1
killed = 0
for i in range(1, int(n) + 1):
	if f[i] > 0:
		killed += 1
q = input_file.readline().strip()
for i in range(int(q)):
	query = input_file.readline().strip().split()
	if query[0] == '3':
		output_file.write(str(n - killed) + '\n')
		continue
	(u, v) = (int(query[1]), int(query[2]))
	(a, b) = (min(u, v), max(u, v))
	if query[0] == '1':
		if f[a] == 0:
			killed += 1
		f[a] += 1
	else:
		f[a] -= 1
		if f[a] == 0:
			killed -= 1


import sys
(n, m) = map(int, sys.stdin.readline().split())
graph = [0] * n
ans = 0
for f in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	graph[min(u, v) - 1] += 1
	if graph[min(u, v) - 1] == 1:
		ans += 1
q = int(sys.stdin.readline())
for qr in range(q):
	arr = list(map(int, sys.stdin.readline().split()))
	if arr[0] == 1:
		graph[min(arr[1], arr[2]) - 1] += 1
		if graph[min(arr[1], arr[2]) - 1] == 1:
			ans += 1
	elif arr[0] == 2:
		graph[min(arr[1], arr[2]) - 1] -= 1
		if graph[min(arr[1], arr[2]) - 1] == 0:
			ans -= 1
	else:
		print(n - ans)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
(n, m) = M()
l = [0] * n
co = n
for i in range(m):
	(a, b) = M()
	t = min(a - 1, b - 1)
	l[t] += 1
	if l[t] == 1:
		co -= 1
q = I()
for i in range(q):
	p = L()
	if len(p) == 3:
		(a, b, c) = (p[0], p[1], p[2])
		if a == 1:
			t = min(b - 1, c - 1)
			l[t] += 1
			if l[t] == 1:
				co -= 1
		else:
			t = min(b - 1, c - 1)
			l[t] -= 1
			if l[t] == 0:
				co += 1
	else:
		print(co)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_int_gen():
	return map(int, input().split())
from collections import defaultdict
(noble_size, friendships) = input_int_gen()
friends = defaultdict(set)
died = 0
for _ in range(friendships):
	(a, b) = input_int_gen()
	if b > a:
		if not friends[a]:
			died += 1
		friends[a].add(b)
	else:
		if not friends[b]:
			died += 1
		friends[b].add(a)
query_size = inp()
for _ in range(query_size):
	query = input_list()
	if query[0] == 1:
		(a, b) = (query[1], query[2])
		if b > a:
			if not friends[a]:
				died += 1
			friends[a].add(b)
		else:
			if not friends[b]:
				died += 1
			friends[b].add(a)
	if query[0] == 2:
		(a, b) = (query[1], query[2])
		if b > a:
			friends[a].remove(b)
			if not friends[a]:
				died -= 1
		else:
			friends[b].remove(a)
			if not friends[b]:
				died -= 1
	if query[0] == 3:
		print(noble_size - died)


(n, m) = map(int, input().split())
g = [0] * n
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	if v > u:
		g[u] += 1
	else:
		g[v] += 1
q = int(input())
answer = sum([1 for i in range(n) if g[i] == 0])
allAnswers = []
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		query[1] -= 1
		query[2] -= 1
		if query[1] > query[2]:
			if g[query[2]] == 0:
				answer -= 1
			g[query[2]] += 1
		else:
			if g[query[1]] == 0:
				answer -= 1
			g[query[1]] += 1
	elif query[0] == 2:
		query[1] -= 1
		query[2] -= 1
		if query[1] > query[2]:
			if g[query[2]] == 1:
				answer += 1
			g[query[2]] -= 1
		else:
			if g[query[1]] == 1:
				answer += 1
			g[query[1]] -= 1
	else:
		allAnswers.append(answer)
for x in allAnswers:
	print(x)


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

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

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	(n, m) = read()
	arr = [0] * (n + 1)
	c = n
	for i in range(m):
		(u, v) = sorted(read())
		if arr[u] == 0:
			c -= 1
		arr[u] += 1
	for _ in range(nin()):
		(mode, *other) = read()
		if mode in (1, 2):
			(u, v) = sorted(other)
			if mode == 1:
				if arr[u] == 0:
					c -= 1
				arr[u] += 1
			else:
				arr[u] -= 1
				if arr[u] == 0:
					c += 1
		else:
			ans_.append(c)
solve()
for i in ans_:
	print(i)


(n, m) = map(lambda x: int(x), input().split())
N = n
E = [0] * (n + 1)
res = []
for _ in range(m):
	(a, b) = sorted(map(lambda x: int(x), input().split()))
	if E[a] == 0:
		N -= 1
	E[a] += 1
Q = int(input())
for _ in range(Q):
	q = input().split()
	if q[0] == '3':
		res.append(N)
	elif q[0] == '1':
		(a, b) = sorted(map(lambda x: int(x), q[1:]))
		if E[a] == 0:
			N -= 1
		E[a] += 1
	else:
		(a, b) = sorted(map(lambda x: int(x), q[1:]))
		E[a] -= 1
		if E[a] == 0:
			N += 1
[print(r) for r in res]


from sys import stdin
input = stdin.readline
from collections import defaultdict
(n, m) = map(int, input().strip().split())
dead = [0] * n
deadcnt = 0
g = defaultdict(set)
for i in range(m):
	(x, y) = map(int, input().strip().split())
	g[x - 1].add(y - 1)
	g[y - 1].add(x - 1)
	if y - 1 > x - 1:
		deadcnt += dead[x - 1] == 0
		dead[x - 1] += 1
	else:
		deadcnt += dead[y - 1] == 0
		dead[y - 1] += 1
for _ in range(int(input())):
	l = list(map(int, input().strip().split()))
	if l[0] == 3:
		print(n - deadcnt)
	elif l[0] == 2:
		x = l[1] - 1
		y = l[2] - 1
		g[x].remove(y)
		g[y].remove(x)
		if y < x:
			(x, y) = (y, x)
		dead[x] -= 1
		if dead[x] == 0:
			deadcnt -= 1
	else:
		(x, y) = (l[1] - 1, l[2] - 1)
		g[x].add(y)
		g[y].add(x)
		if y < x:
			(x, y) = (y, x)
		deadcnt += dead[x] == 0
		dead[x] += 1


(n, m) = map(int, input().split())
g = []
c1 = []
c2 = []
for i in range(n):
	c1.append(0)
	c2.append(0)
q = [1] * n
for i in range(m):
	(a, b) = map(lambda z: int(z) - 1, input().split())
	(a, b) = (min(a, b), max(a, b))
	c1[a] += 1
	c2[b] += 1
	q[a] = 0
cur = sum(q)
ans = []
for _ in range(int(input())):
	inp = input()
	if inp[0] == '3':
		ans.append(cur)
		continue
	(t, u, v) = map(lambda z: int(z) - 1, inp.split())
	(u, v) = (min(u, v), max(u, v))
	if t == 0:
		c1[u] += 1
		c2[v] += 1
		if q[u] == 1:
			q[u] = 0
			cur -= 1
	else:
		c1[u] -= 1
		c2[v] -= 1
		if c1[u] == 0 and q[u] == 0:
			q[u] = 1
			cur += 1
print('\n'.join(map(str, ans)))


import sys

def input():
	s = sys.stdin.readline()
	return s
(n, m) = map(int, input().strip().split())
nodes = [set() for i in range(1 + n)]
empty_sets = n
pairs = []
for i in range(m):
	(f, t) = sorted(list(map(int, input().strip().split())))
	if len(nodes[f]) == 0:
		empty_sets -= 1
	nodes[f].add(t)
q = int(input())
qs = []
for i in range(q):
	nums = list(map(int, input().strip().split()))
	qs.append(nums)
for nums in qs:
	if nums[0] == 3:
		print(empty_sets)
	else:
		(f, t) = sorted(nums[1:])
		if nums[0] == 1:
			if len(nodes[f]) == 0:
				empty_sets -= 1
			nodes[f].add(t)
		else:
			nodes[f].remove(t)
			if len(nodes[f]) == 0:
				empty_sets += 1


(n, m) = map(int, input().strip().split())
nodes = [set() for i in range(1 + n)]
empty_sets = n
pairs = []
for i in range(m):
	(f, t) = sorted(list(map(int, input().strip().split())))
	if len(nodes[f]) == 0:
		empty_sets -= 1
	nodes[f].add(t)
q = int(input())
qs = []
for i in range(q):
	nums = list(map(int, input().strip().split()))
	qs.append(nums)
for nums in qs:
	if nums[0] == 3:
		print(empty_sets)
	else:
		(f, t) = sorted(nums[1:])
		if nums[0] == 1:
			if len(nodes[f]) == 0:
				empty_sets -= 1
			nodes[f].add(t)
		else:
			nodes[f].remove(t)
			if len(nodes[f]) == 0:
				empty_sets += 1


(n, m) = [int(i) for i in input().split()]
nobles = [0 for i in range(n)]
for i in range(m):
	(u, v) = [int(i) - 1 for i in input().split()]
	if u > v:
		(u, v) = (v, u)
	if nobles[u] == 0:
		n -= 1
	nobles[u] += 1
m = int(input())
for i in range(m):
	u = input()
	if u == '3':
		print(n)
	elif u[0] == '1':
		v = int(u.split()[2]) - 1
		u = int(u.split()[1]) - 1
		if u > v:
			(u, v) = (v, u)
		if nobles[u] == 0:
			n -= 1
		nobles[u] += 1
	else:
		v = int(u.split()[2]) - 1
		u = int(u.split()[1]) - 1
		if u > v:
			(u, v) = (v, u)
		nobles[u] -= 1
		if nobles[u] == 0:
			n += 1


(n, m) = map(int, input().split())
arr = [0 for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	if u > v:
		arr[v - 1] += 1
	else:
		arr[u - 1] += 1
q = int(input())
ans = 0
for i in arr:
	if i == 0:
		ans += 1
for i in range(q):
	temp2 = input()
	if temp2 != '3':
		(a, u, v) = map(int, temp2.split())
		if a == 1:
			if u > v:
				if arr[v - 1] == 0:
					ans -= 1
				arr[v - 1] += 1
			else:
				if arr[u - 1] == 0:
					ans -= 1
				arr[u - 1] += 1
		elif a == 2:
			if u > v:
				arr[v - 1] -= 1
				if arr[v - 1] == 0:
					ans += 1
			else:
				arr[u - 1] -= 1
				if arr[u - 1] == 0:
					ans += 1
	else:
		print(ans)


from typing import BinaryIO

def main():
	for i in range(1):
		solve()

def solve():
	(n, m) = pair()
	bigger = [0 for i in range(n)]
	for i in range(m):
		(u, v) = pair()
		bigger[min(u, v) - 1] += 1
	ans = find(bigger)
	q = num()
	for i in range(q):
		s = input()
		if s == '3':
			print(ans)
		else:
			(k, u, v) = map(int, s.split())
			if k == 1:
				bigger[min(u, v) - 1] += 1
				if bigger[min(u, v) - 1] == 1:
					ans -= 1
			else:
				bigger[min(u, v) - 1] -= 1
				if bigger[min(u, v) - 1] == 0:
					ans += 1

def find(array):
	ans = 0
	for i in range(len(array)):
		if array[i] == 0:
			ans += 1
	return ans
import itertools
import bisect, math
import copy
import fractions

def s(e):
	return sum(e)

def l(e):
	return len(e)

def num():
	return int(input())

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

def pair():
	return map(int, input().split())

def p(x='', end='\n'):
	return print(x, end=end)

def sort(a):
	return sorted(a)

def fpair(x):
	return str(fractions.Fraction(x)).split('/')

def parray(a):
	for i in a:
		p(i, end=' ')
	p()
main()


arr = input().split()
n = int(arr[0])
m = int(arr[1])
list_frd = []
for i in range(n):
	list_frd.append(0)
nobles = n
for i in range(m):
	arr = input().split(' ')
	s = int(arr[0])
	b = int(arr[1])
	if s > b:
		(s, b) = (b, s)
	s = s - 1
	if list_frd[s] == 0:
		nobles = nobles - 1
	list_frd[s] = list_frd[s] + 1
q = int(input())
for i in range(q):
	arr = input().split()
	if len(arr) == 1:
		print(nobles)
	elif int(arr[0]) == 1:
		s = int(arr[1])
		b = int(arr[2])
		if s > b:
			(s, b) = (b, s)
		s = s - 1
		if list_frd[s] == 0:
			nobles = nobles - 1
		list_frd[s] = list_frd[s] + 1
	else:
		s = int(arr[1])
		b = int(arr[2])
		if s > b:
			(s, b) = (b, s)
		s = s - 1
		list_frd[s] = list_frd[s] - 1
		if list_frd[s] == 0:
			nobles = nobles + 1


(n, m) = map(int, input().split())
a = [0] * n
for _ in range(m):
	(b, c) = map(int, input().split())
	a[min(b, c)] += 1
z = 0
for i in a:
	if i == 0:
		z += 1
s1 = z
v = list(a)
q = int(input())
for _ in range(q):
	t = input()
	if t[0] == '3':
		print(s1)
	else:
		(query, b, c) = map(int, t.split())
		if query == 1:
			v[min(b, c)] += 1
			if v[min(b, c)] == 1:
				s1 -= 1
		else:
			v[min(b, c)] -= 1
			if v[min(b, c)] == 0:
				s1 += 1


def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())
for _ in range(1):
	(n, m) = mi()
	ans = 0
	res = [0] * (n + 1)
	for i in range(m):
		(u, v) = mi()
		u = min(u, v)
		res[u] += 1
	for i in range(1, n + 1):
		if res[i] > 0:
			ans += 1
	q = ii()
	for i in range(q):
		s = input().split()
		if s[0] == '3':
			print(n - ans)
		elif s[0] == '1':
			u = int(s[1])
			v = int(s[2])
			u = min(u, v)
			if res[u] > 0:
				res[u] += 1
			else:
				ans += 1
				res[u] += 1
		elif s[0] == '2':
			u = int(s[1])
			v = int(s[2])
			u = min(u, v)
			if res[u] == 1:
				ans -= 1
				res[u] -= 1
			else:
				res[u] -= 1


(n, m) = map(int, input().split())
seen = [0] * (n + 1)
ans = n
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = sorted([u, v])
	seen[u] += 1
	if seen[u] == 1:
		ans -= 1
q = int(input())
for i in range(q):
	row = input()
	if len(row) == 1:
		print(ans)
	else:
		(k, u, v) = map(int, row.split())
		(u, v) = sorted([u, v])
		if k == 1:
			seen[u] += 1
			if seen[u] == 1:
				ans -= 1
		else:
			seen[u] -= 1
			if seen[u] == 0:
				ans += 1


A = list(map(int, input().split()))
(n, m) = (A[0], A[1])
dic = [0 for _ in range(n + 1)]
ans = 0
for _ in range(m):
	A = list(map(int, input().split()))
	minn = min(A)
	if dic[minn] == 0:
		ans += 1
	dic[minn] += 1
x = int(input())
for _ in range(x):
	A = input()
	if len(A) == 1:
		print(n - ans)
	elif A[0] == '1':
		A = list(map(int, A.split()))
		minn = min(A[1:])
		if dic[minn] == 0:
			ans += 1
		dic[minn] += 1
	elif A[0] == '2':
		A = list(map(int, A.split()))
		minn = min(A[1:])
		dic[minn] -= 1
		if dic[minn] == 0:
			ans -= 1


(n, m) = map(int, input().split())
frens = [0 for __ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	if u > v:
		frens[v] += 1
	else:
		frens[u] += 1
alive = 0
for i in range(1, n + 1):
	if frens[i] == 0:
		alive += 1
for ___ in range(int(input())):
	inp = input().strip()
	if len(inp) == 1:
		print(max(alive, 0))
	else:
		(a, b, c) = map(int, inp.split())
		if a == 1:
			if b > c:
				if frens[c] == 0:
					alive -= 1
				frens[c] += 1
			else:
				if frens[b] == 0:
					alive -= 1
				frens[b] += 1
		elif b > c:
			frens[c] -= 1
			if frens[c] == 0:
				alive += 1
		else:
			frens[b] -= 1
			if frens[b] == 0:
				alive += 1


(n, m) = map(int, input().split())
x = [0] * n
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	if u < v:
		x[u] += 1
	else:
		x[v] += 1
c = 0
for i in range(n):
	if x[i] == 0:
		c += 1
q = int(input())
while q:
	q -= 1
	s = input()
	if len(s) == 1:
		print(c)
		continue
	else:
		(y, u, v) = map(int, s.split())
		u -= 1
		v -= 1
		if y == 1:
			if u < v:
				if x[u] == 0:
					c -= 1
				x[u] += 1
			else:
				if x[v] == 0:
					c -= 1
				x[v] += 1
		elif u < v:
			x[u] -= 1
			if x[u] == 0:
				c += 1
		else:
			x[v] -= 1
			if x[v] == 0:
				c += 1


from collections import defaultdict
(n, m) = map(int, input().split())
weak_map = defaultdict(int)
for i in range(m):
	(a, b) = map(int, input().split())
	weak_map[min(a, b)] += 1
k = int(input())
for _ in range(k):
	q = input()
	if len(q) == 1:
		print(n - len(weak_map))
	else:
		(ty, a, b) = map(int, q.split())
		if ty == 1:
			weak_map[min(a, b)] += 1
		else:
			weak_map[min(a, b)] -= 1
			if weak_map[min(a, b)] == 0:
				del weak_map[min(a, b)]


(n, m) = map(int, input().split())
higher_friends = [0 for i in range(n)]
alive = n
for i in range(m):
	(a, b) = map(int, input().split())
	if a > b:
		if higher_friends[b - 1] == 0:
			alive -= 1
		higher_friends[b - 1] += 1
	else:
		if higher_friends[a - 1] == 0:
			alive -= 1
		higher_friends[a - 1] += 1
query = int(input())
for i in range(query):
	s = input()
	if s[0] == '1':
		(a, b) = map(int, s[2:].split())
		if a > b:
			if higher_friends[b - 1] == 0:
				alive -= 1
			higher_friends[b - 1] += 1
		else:
			if higher_friends[a - 1] == 0:
				alive -= 1
			higher_friends[a - 1] += 1
	elif s[0] == '2':
		(a, b) = map(int, s[2:].split())
		if a > b:
			higher_friends[b - 1] -= 1
			if higher_friends[b - 1] == 0:
				alive += 1
		else:
			higher_friends[a - 1] -= 1
			if higher_friends[a - 1] == 0:
				alive += 1
	else:
		print(alive)


(n, m) = map(int, input().split())
a = [0 for i in range(n)]
for i in range(m):
	(ar, b) = map(int, input().split())
	x = min(ar, b)
	a[x] += 1
s = 0
for i in a:
	if i == 0:
		s += 1
at = a
g = 1
st = int(s)
for q in range(int(input())):
	t = input()
	if t[0] == '3':
		print(st)
	else:
		(qn, ar, b) = map(int, t.split())
		if qn == 1:
			x = min(ar, b)
			at[x] += 1
			if at[x] == 1:
				st -= 1
		else:
			x = min(ar, b)
			at[x] -= 1
			if at[x] == 0:
				st += 1


from collections import defaultdict
while True:
	try:
		bigger = defaultdict(int)
		(n, m) = map(int, input().strip().split())
		killed = 0
		for _ in range(m):
			(a, b) = map(int, input().strip().split())
			if a > b:
				(a, b) = (b, a)
			if bigger[a] == 0:
				killed += 1
			bigger[a] += 1
		q = int(input().strip())
		for _ in range(q):
			line = input().strip()
			if line[0] == '3':
				print(n - killed)
			else:
				(op, u, v) = map(int, line.split())
				if op == 1:
					if u > v:
						(u, v) = (v, u)
					if bigger[u] == 0:
						killed += 1
					bigger[u] += 1
				else:
					if u > v:
						(u, v) = (v, u)
					bigger[u] -= 1
					if bigger[u] == 0:
						killed -= 1
	except EOFError:
		break


ANS = 0
DEG = []

def add(u, v):
	global ANS, DEG
	if u > v:
		(u, v) = (v, u)
	ANS -= DEG[u] == 0
	DEG[u] += 1

def del_(u, v):
	global ANS, DEG
	if u > v:
		(u, v) = (v, u)
	DEG[u] -= 1
	ANS += DEG[u] == 0

def main():
	global ANS, DEG
	(n, m) = map(int, input().split())
	ANS = n
	DEG = [0] * n
	for _ in range(m):
		(u, v) = map(int, input().split())
		add(u, v)
	q = int(input())
	for _ in range(q):
		s = input().split()
		c = int(s[0])
		if c == 1:
			(u, v) = map(int, s[1:])
			add(u, v)
		elif c == 2:
			(u, v) = map(int, s[1:])
			del_(u, v)
		elif c == 3:
			print(ANS)
		else:
			raise NotImplementedError
main()


(n, m) = map(int, input().split())
di = [0] * (n + 2)
dead = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	if di[a] == 0:
		dead += 1
	di[a] += 1
q = int(input())
for _ in range(q):
	st = input()
	if st == '3':
		print(n - dead)
	else:
		(x, a, b) = map(int, st.split())
		if x == 1:
			if a > b:
				(a, b) = (b, a)
			if di[a] == 0:
				dead += 1
			di[a] += 1
		else:
			if a > b:
				(a, b) = (b, a)
			if di[a] == 1:
				dead -= 1
			di[a] -= 1


from collections import defaultdict
A = list(map(int, input().split()))
(n, m) = (A[0], A[1])
dic = defaultdict(int)
for _ in range(m):
	A = list(map(int, input().split()))
	minn = min(A)
	dic[minn] += 1
x = int(input())
for _ in range(x):
	A = input()
	if A[0] == '1':
		A = list(map(int, A.split()))
		minn = min(A[1:])
		dic[minn] += 1
	elif A[0] == '2':
		A = list(map(int, A.split()))
		minn = min(A[1:])
		dic[minn] -= 1
		if dic[minn] == 0:
			del dic[minn]
	else:
		print(n - len(dic))


from copy import deepcopy
(n, m) = map(int, input().split())
d = [0 for i in range(1, n + 1)]
p = set()
for _ in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (max(x, y), min(x, y))
	d[y - 1] += 1
	p.add(y)
r = n - len(p)
rr = r
for _ in range(int(input())):
	n = input()
	if n == '3':
		print(r)
	else:
		n = n.split()
		(x, y) = (int(n[1]), int(n[2]))
		if n[0] == '1':
			if d[min(x, y) - 1] == 0:
				r -= 1
			d[min(x, y) - 1] += 1
		else:
			if d[min(x, y) - 1] == 1:
				r += 1
			d[min(x, y) - 1] -= 1


(n, m) = map(int, input().split())
a = [0] * n
ot = 0
for i in range(m):
	(u, v) = map(int, input().split())
	b = min(u, v)
	a[b - 1] += 1
	if a[b - 1] == 1:
		ot += 1
q = int(input())
for i in range(q):
	s = input()
	if s[0] == '3':
		print(n - ot)
	if s[0] != '3':
		(x, y, z) = map(int, s.split())
		if x == 1:
			a[min(y, z) - 1] += 1
			if a[min(y, z) - 1] == 1:
				ot += 1
		else:
			a[min(y, z) - 1] -= 1
			if a[min(y, z) - 1] == 0:
				ot -= 1


(a, m) = map(int, input().split())
c = [0] * (a + 1)
for _ in range(m):
	(u, v) = map(int, input().split())
	z = min(u, v)
	if c[z] == 0:
		a -= 1
	c[z] += 1
for _ in range(int(input())):
	tes = input().split()
	if len(tes) == 1:
		print(a)
	else:
		(x, u, v) = map(int, tes)
		if x == 1:
			z = min(u, v)
			if c[z] == 0:
				a -= 1
			c[z] += 1
		else:
			z = min(u, v)
			if c[z] == 1:
				a += 1
			c[u] -= 1


(n, m) = map(int, input().split())
g = [0] * (n + 1)
dead = 0
for i in range(m):
	(x, y) = map(int, input().split())
	if x > y:
		weak = y
	else:
		weak = x
	g[weak] += 1
	if g[weak] == 1:
		dead += 1
for q in range(int(input())):
	miku = input().split()
	if len(miku) == 1:
		print(n - dead)
		continue
	(typ, x, y) = map(int, miku)
	if x > y:
		weak = y
	else:
		weak = x
	if typ == 1:
		g[weak] += 1
		if g[weak] == 1:
			dead += 1
	if typ == 2:
		g[weak] -= 1
		if g[weak] == 0:
			dead -= 1


(n, m) = list(map(int, input().split()))
arr = [1] * n
frnd = [0] * n
for _ in range(m):
	(x, y) = list(map(int, input().split()))
	if x > y:
		arr[y] = 0
		frnd[y] += 1
	else:
		arr[x] = 0
		frnd[x] += 1
ans = frnd.count(0)
tem = 0
temp = 0
q = int(input())
for _ in range(q):
	tem = input().split()
	if len(tem) == 1:
		print(ans)
	elif int(tem[0]) == 2:
		temp = min(int(tem[1]), int(tem[2]))
		frnd[temp] -= 1
		if frnd[temp] == 0:
			ans += 1
	else:
		temp = min(int(tem[1]), int(tem[2]))
		frnd[temp] += 1
		if frnd[temp] == 1:
			ans -= 1


(n, m) = map(int, input().split())
ar = [0 for _ in range(n + 1)]
ans = n
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (min(u, v), max(u, v))
	if ar[u] == 0:
		ans -= 1
	ar[u] += 1
q = int(input())
for _ in range(q):
	inp = input()
	if inp[0] == '1':
		(_, u, v) = inp.split()
		(u, v) = (min(int(u), int(v)), max(int(u), int(v)))
		if ar[u] == 0:
			ans -= 1
		ar[u] += 1
	elif inp[0] == '2':
		(_, u, v) = inp.split()
		(u, v) = (min(int(u), int(v)), max(int(u), int(v)))
		ar[u] -= 1
		if ar[u] == 0:
			ans += 1
	else:
		print(ans)


from collections import defaultdict
(n, m) = map(int, input().split())
degree = defaultdict(int)
ans = n
for _ in range(m):
	(s, d) = map(int, input().split())
	(s, d) = (min(s, d), max(s, d))
	if degree[s] == 0:
		ans -= 1
	degree[s] += 1
q = int(input())
for _ in range(q):
	d = input()
	if len(d) == 1:
		print(ans)
	else:
		(o, s, g) = map(int, d.split())
		if o == 1:
			(s, g) = (min(s, g), max(s, g))
			if degree[s] == 0:
				ans -= 1
			degree[s] += 1
		else:
			(s, g) = (min(s, g), max(s, g))
			if degree[s] == 1:
				ans += 1
			degree[s] -= 1


def solution():
	(n, m) = map(int, input().split())
	greater = {node: set() for node in range(1, n + 1)}
	freeNodes = set([node for node in greater])
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a < b:
			(a, b) = (b, a)
		greater[b].add(a)
		if b in freeNodes:
			freeNodes.remove(b)
	q = int(input())
	for _ in range(q):
		c = input()
		if len(c) == 1:
			print(len(freeNodes))
			continue
		(op, a, b) = map(int, c.split())
		if a < b:
			(a, b) = (b, a)
		if op == 1:
			greater[b].add(a)
			if b in freeNodes:
				freeNodes.remove(b)
		elif op == 2:
			if a in greater[b]:
				greater[b].remove(a)
				if len(greater[b]) == 0:
					freeNodes.add(b)
import sys
import threading
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
thread = threading.Thread(target=solution)
thread.start()
thread.join()


def solve():
	(n, m) = map(int, input().split())
	ans = dict()
	for i in range(m):
		(u, v) = map(int, input().split())
		if u > v:
			if v in ans:
				ans[v] += 1
			else:
				ans[v] = 1
		elif u in ans:
			ans[u] += 1
		else:
			ans[u] = 1
	q = int(input())
	res = len(ans)
	for _ in range(q):
		temp = list(map(int, input().split()))
		t = temp[0]
		if t == 2:
			(u, v) = (temp[1], temp[2])
			if u > v:
				ans[v] -= 1
				if ans[v] == 0:
					del ans[v]
					res -= 1
			else:
				ans[u] -= 1
				if ans[u] == 0:
					del ans[u]
					res -= 1
		elif t == 1:
			(u, v) = (temp[1], temp[2])
			if u > v:
				if v in ans:
					ans[v] += 1
				else:
					ans[v] = 1
					res += 1
			elif u in ans:
				ans[u] += 1
			else:
				ans[u] = 1
				res += 1
		else:
			print(n - res)
t = 1
for i in range(t):
	solve()


for _ in range(1):
	(n, m) = map(int, input().split())
	mp = dict()
	for i in range(m):
		(x, y) = map(int, input().split())
		(x, y) = (max(x, y), min(x, y))
		if y in mp:
			mp[y] += 1
		else:
			mp[y] = 1
	q = int(input())
	for h in range(q):
		qu = input()
		if qu[0] == '3':
			print(n - len(mp))
		else:
			(t, x, y) = map(int, qu.split())
			if t == 1:
				(x, y) = (max(x, y), min(x, y))
				if y in mp:
					mp[y] += 1
				else:
					mp[y] = 1
			else:
				(x, y) = (max(x, y), min(x, y))
				mp[y] -= 1
				if mp[y] == 0:
					del mp[y]


(n, m) = list(map(int, input().split()))
w = [0 for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	if u > v:
		w[v - 1] += 1
	else:
		w[u - 1] += 1
ans = w.count(0)
for _ in range(int(input())):
	s = list(map(int, input().split()))
	if s[0] == 3:
		print(ans)
	elif s[0] == 1:
		if s[1] > s[2]:
			w[s[2] - 1] += 1
			if w[s[2] - 1] == 1:
				ans -= 1
		else:
			w[s[1] - 1] += 1
			if w[s[1] - 1] == 1:
				ans -= 1
	elif s[1] > s[2]:
		w[s[2] - 1] -= 1
		if w[s[2] - 1] == 0:
			ans += 1
	else:
		w[s[1] - 1] -= 1
		if w[s[1] - 1] == 0:
			ans += 1


(n, m) = map(int, input().split())
small = [0] * (n + 1)
big = [0] * (n + 1)
for i in range(m):
	(u, v) = map(int, input().split())
	small[max(u, v)] += 1
	big[min(u, v)] += 1
ans = 0
for i in range(1, n + 1):
	if big[i] == 0:
		ans += 1
q = int(input())
for i in range(q):
	ch = input().split(' ')
	if ch[0] == '1':
		u = int(ch[1])
		v = int(ch[2])
		if big[min(u, v)] == 0:
			ans -= 1
		small[max(u, v)] += 1
		big[min(u, v)] += 1
	elif ch[0] == '2':
		u = int(ch[1])
		v = int(ch[2])
		small[max(u, v)] -= 1
		big[min(u, v)] -= 1
		if big[min(u, v)] == 0:
			ans += 1
	else:
		print(ans)


(n, m) = [int(i) for i in input().split(' ')]
vin = {}
vout = {}
ans = 0
for i in range(1, n + 1):
	vin[i] = 0
	vout[i] = 0
for i in range(m):
	(u, v) = [int(j) for j in input().split(' ')]
	if u > v:
		vout[u] += 1
		vin[v] += 1
	else:
		vout[v] += 1
		vin[u] += 1
for i in vin:
	if vin[i] == 0:
		ans += 1
q = int(input())
for i in range(q):
	s = input()
	if len(s) > 1:
		(a, u, v) = [int(j) for j in s.split(' ')]
	else:
		a = 3
	if a == 1:
		if u > v:
			vout[u] += 1
			vin[v] += 1
			if vin[v] == 1:
				ans -= 1
		else:
			vout[v] += 1
			vin[u] += 1
			if vin[u] == 1:
				ans -= 1
	elif a == 2:
		if u > v:
			vout[u] -= 1
			vin[v] -= 1
			if vin[v] == 0:
				ans += 1
		else:
			vout[v] -= 1
			vin[u] -= 1
			if vin[u] == 0:
				ans += 1
	else:
		print(ans)


from collections import defaultdict

def test():
	(n, m) = map(int, input().split())
	c = defaultdict(int)
	for i in range(m):
		(u, v) = map(int, input().split())
		x = min(u, v)
		c[x] += 1
	p = 0
	for i in range(1, n + 1):
		if c[i] > 0:
			p += 1
	q = int(input())
	for i in range(q):
		l = list(map(int, input().split()))
		if l[0] < 3:
			if l[0] == 1:
				x = min(l[1], l[2])
				if c[x] == 0:
					p += 1
				c[x] += 1
			else:
				x = min(l[1], l[2])
				c[x] -= 1
				if c[x] == 0:
					p -= 1
		else:
			print(n - p)
t = 1
while t:
	test()
	t -= 1


(n, m) = map(int, input().split())
stronger = [0] * (n + 1)
total = 0
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (min(u, v), max(u, v))
	stronger[u] += 1
	if stronger[u] == 1:
		total += 1
query = int(input())
for q in range(query):
	X = input().split()
	(i, u, v) = (int(X[0]), None, None)
	if len(X) > 1:
		u = int(X[1])
		v = int(X[2])
	if i == 3:
		print(n - total)
	elif i == 1:
		(u, v) = (min(u, v), max(u, v))
		stronger[u] += 1
		if stronger[u] == 1:
			total += 1
	else:
		(u, v) = (min(u, v), max(u, v))
		stronger[u] -= 1
		if stronger[u] == 0:
			total -= 1


(m, n) = map(int, input().split())
l = [0] * (m + 1)
ans = 0
for i in range(n):
	(u, v) = map(int, input().split())
	if u > v:
		(u, v) = (v, u)
	l[u] += 1
	if l[u] == 1:
		ans += 1
q = int(input())
for i in range(q):
	li = list(map(int, input().split()))
	if len(li) == 1:
		print(m - ans)
		continue
	if li[0] == 1:
		if li[1] > li[2]:
			(li[1], li[2]) = (li[2], li[1])
		l[li[1]] += 1
		if l[li[1]] == 1:
			ans += 1
	elif li[0] == 2:
		if li[1] > li[2]:
			(li[1], li[2]) = (li[2], li[1])
		l[li[1]] -= 1
		if l[li[1]] == 0:
			ans -= 1


q = list(map(int, input().split()))
a = [0 for _ in range(q[0])]
res = q[0]
for _ in range(q[1]):
	x = min(list(map(int, input().split())))
	res -= 1 if a[x] == 0 else 0
	a[x] += 1
for _ in range(int(input())):
	x = input().split()
	if x[0] == '1':
		x = min(int(x[1]), int(x[2]))
		res -= 1 if a[x] == 0 else 0
		a[x] += 1
	elif x[0] == '2':
		x = min(int(x[1]), int(x[2]))
		a[x] -= 1
		res += 1 if a[x] == 0 else 0
	else:
		print(res)