In a market of mangoes, there are N sellers numbered from 1 to N. The i-th seller initially charges a price of A_{i} coins for each of their mangoes. However, the sellers are very competitive, and they will change prices based on other sellers nearby.

You have a simple graph (unweighted, undirected graph containing no self-loops or multiple edges) G with N vertices and M edges. There is an edge between two sellers if and only if they are neighbours. When you buy a mango from a seller numbered X, the following occurs:

Seller X keeps his price the same.
Every seller Y who is a neighbour of X increases their price by 1, that is, A_{Y} = A_{Y} + 1 for every Y who is a neighbour of X.
Every other seller Z who is not a neighbour of X decreases their price by 1; that is, A_{Z} = A_{Z} - 1 for every Z who is not a neighbour of X.

Prices can become zero or negative during this process.

Now you should process Q queries of the following three types:
\texttt{+} u v — Add an edge between nodes u and v in the graph. It's guaranteed there is no edge between u and v currently.
\texttt{-} u v — Remove an edge between nodes u and v in the graph. It's guaranteed there is an edge between u and v currently.
\texttt{?} — Find the minimum amount of money you need to pay so that you can buy exactly one mango from every seller. After queries of this type, the prices of all sellers are reset to their initial value.

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

- The first line contains two integers N and M - the number of sellers and the number of edges in the graph.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the price array A.
- The next M lines each contain two integers u and v (1 ≤ u,v ≤ N, u \ne v), representing an edge of G. 
- The next line contains the integer Q — the number of queries. 
- The next Q lines contain the queries. Each query is in the format given in the problem statement.
- There is at least one query of type \texttt{?}.

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

For each query of type \texttt{?}, output one integer — the minimum amount of money you need to pay so that you can buy exactly one mango from each seller.

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

$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ M ≤ \min(\binom{N}{2}, 10^{5})$
$1 ≤ A_{i} ≤ 10^{9}$
- It's guaranteed that $G$ is a simple graph, that is, it is an unweighted, undirected graph containing no self-loops or multiple edges.

----- Sample Input 1 ------ 
4 3
8 9 6 10
2 1
1 3
3 4
6
?
+ 2 3
+ 4 2
- 3 1
+ 1 4
?

----- Sample Output 1 ------ 
33
37

----- explanation 1 ------ 
In the sample test, the first query of type $\texttt{?}$ is pictured below. The $i$-th node (from left to right) contains the price of the $i$-th seller. If we buy mangoes from the sellers $1$, $4$, $3$, $2$, in that order, then we can pay $8$, $9$, $8$, and $8$ coins for the mangoes, respectively, paying a total $33$ coins. It can be proven that this is indeed the minimum amount possible.

It can be proven that for the second query of type $\texttt{?}$, the minimum amount we can pay is $37$ coins. Note that the prices of the mangoes reset after each query of type $\texttt{?}$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures


Solutions:
import sys, os, io
import math
from collections import defaultdict, deque

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

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = li()
a = li()
g = [[] for i in range(n)]
s = sum(a)
for i in range(m):
	(a, b) = li()
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
q = ii()
c = m
for i in range(q):
	l = [x for x in input().split()]
	if l[0] == '?':
		print(s - n * (n - 1) // 2 + 2 * c)
	elif l[0] == '+':
		c += 1
	else:
		c -= 1


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(m):
	(x, y) = map(int, input().split())
ans = sum(a)
tot = n * (n - 1) // 2
for _ in range(int(input())):
	q = list(map(str, input().split()))
	if len(q) != 3:
		print(ans + 2 * m - tot)
		continue
	if q[0] == '+':
		m += 1
	else:
		m -= 1


(n, m) = map(int, input().split())
arr = [int(i) for i in input().split()]
sumo = sum(arr)
no = m
for i in range(m):
	input()
q = int(input())
for i in range(q):
	s = input()[0]
	if s == '+':
		no += 1
	elif s == '-':
		no -= 1
	else:
		print(sumo + 2 * no - n * (n - 1) // 2)


import sys
import math
from collections import defaultdict, Counter
from bisect import *
from string import ascii_lowercase

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def solve():
	(n, m) = readInts()
	a_c = readList(int)
	s = sum(a_c)
	for _ in range(m):
		input()
	q = readInts()
	for _ in range(q):
		temp = input()
		if temp[0] == '+':
			m += 1
		elif temp[0] == '-':
			m -= 1
		else:
			print(s - n * (n - 1) // 2 + 2 * m)

def main():
	t = 1
	for _ in range(t):
		solve()
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
val = sum(a) - n * (n - 1) // 2
edge = m
for i in range(m):
	(u, v) = map(int, input().split())
for i in range(int(input())):
	data = list(map(str, input().split()))
	if data[0] == '?':
		print(val + 2 * edge)
	elif data[0] == '+':
		edge += 1
	else:
		edge -= 1


from sys import stdin
input = stdin.readline

def answer():
	s = sum(a)
	d = sum(deg)
	nd = sum(nondeg[1:n + 1])
	for i in range(int(input())):
		opp = input().split()
		if opp[0] == '?':
			print(s + d // 2 - nd // 2)
		if opp[0] == '+':
			(u, v) = (int(opp[1]), int(opp[2]))
			d += 2
			nd -= 2
		if opp[0] == '-':
			(u, v) = (int(opp[1]), int(opp[2]))
			d -= 2
			nd += 2
for T in range(1):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	deg = [0 for i in range(n + 1)]
	nondeg = [n - 1 for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		deg[u] += 1
		deg[v] += 1
		nondeg[u] -= 1
		nondeg[v] -= 1
	answer()


(n, m) = map(int, input().split())
x = [int(w) for w in input().split()]
edges = 0
for i in range(m):
	(a, b) = map(int, input().split())
	edges += 1
total = n * (n - 1) // 2
q = int(input())
ans = sum(x)
for u in range(q):
	s = [w for w in input().split()]
	if s[0] == '?':
		print(ans + 2 * edges - total)
	elif s[0] == '+':
		edges += 1
	elif s[0] == '-':
		edges -= 1


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
ad = {i + 1: 0 for i in range(n)}
ad2 = {i + 1: [] for i in range(n)}
for i in range(m):
	(p, q) = map(int, input().split())
	ad2[p].append(q)
	ad2[q].append(p)
	ad[p] += 1
	ad[q] += 1
res = 0
for i in a:
	res += i
temp = n
for i in ad:
	res += ad[i] - (temp - 1 - ad[i])
	for j in ad2[i]:
		ad[j] -= 1
	temp -= 1
for i in range(int(input())):
	x = input()
	if x[0] == '+':
		res += 2
	elif x[0] == '-':
		res -= 2
	else:
		print(res)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	for __ in range(how_much_noob_I_am):
		(n, m) = sep()
		arr = lis()
		for i in range(m):
			sep()
		tot = n * (n - 1) // 2
		q = inpu()
		s = sum(arr)
		cnt = m
		for i in range(q):
			p = stringlis()
			if p[0] == '?':
				sub = tot - cnt
				print(s + (cnt - sub))
			elif p[0] == '+':
				cnt += 1
			else:
				cnt -= 1
main()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
x = sum(arr)
edges = 0
remain = n * (n - 1) // 2
for _ in range(k):
	(a, b) = map(int, input().split())
	edges += 1
	remain -= 1
q = int(input())
for _ in range(q):
	t = input().split()
	if t[0] == '+':
		edges += 1
		remain -= 1
	elif t[0] == '-':
		edges -= 1
		remain += 1
	else:
		print(x + edges - remain)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
for _ in range(m):
	(a, b) = map(int, input().split())
ans = sum(arr)
tot = n * (n - 1) // 2
for _ in range(int(input())):
	sab = list(map(str, input().split()))
	if len(sab) != 3:
		print(ans + 2 * m - tot)
		continue
	if sab[0] == '+':
		m += 1
	else:
		m -= 1


import sys
import os
import math
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 = 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

def powmod(a, b, p):
	a %= p
	if a == 0:
		return 0
	prod = 1
	while b > 0:
		if b & 1:
			prod *= a
			prod %= p
			b -= 1
		a *= a
		a %= p
		b //= 2
	return prod

def inv(a, p):
	return powmod(a, p - 2, p)

def nck(n, k, p):
	return fact[n] * inv(fact[k], p) % p * inv(fact[n - k], p) % p

def last_elem(lvl):
	return (lvl + 1) * lvl // 2

def get_lvl(n):
	lvl = -1
	idx = -1
	if n == 1:
		return [1, 1]
	st = 2
	end = 1 + ceil(sqrt(2 * n))
	while st <= end:
		lvl = (st + end) // 2
		if last_elem(lvl) >= n and last_elem(lvl - 1) < n:
			break
		elif last_elem(lvl) > n:
			end = lvl - 1
		else:
			st = lvl + 1
	idx = n - lvl * (lvl - 1) // 2
	return [lvl, idx]

def buildTree(a, s, e, tree, ind):
	if s == e:
		tree[ind] = a[s]
		return
	mid = (s + e) // 2
	buildTree(a, s, mid, tree, 2 * ind)
	buildTree(a, mid + 1, e, tree, 2 * ind + 1)
	tree[ind] = tree[2 * ind] + tree[2 * ind + 1]
	return

def query(tree, ss, se, qs, qe, ind):
	if ss >= qs and se <= qe:
		return tree[ind]
	if qe < ss or qs > se:
		return 0
	mid = (ss + se) // 2
	left = query(tree, ss, mid, qs, qe, 2 * ind)
	right = query(tree, mid + 1, se, qs, qe, 2 * ind + 1)
	return left + right
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 solve():
	(n, m) = inp()
	a = lis()
	for i in range(m):
		(u, v) = inp()
	m *= 2
	sm = sum(a)
	sm -= n * (n - 1) // 2
	q = int(input())
	for i in range(q):
		p = list(input().split())
		if p[0] == '+':
			m += 2
		elif p[0] == '-':
			m -= 2
		else:
			print(sm + m)
t = 1
for _ in range(t):
	solve()


from sys import stdin, stdout
input = stdin.readline
(n, m) = map(int, input().split())
maxi = n * (n - 1) // 2
arr = [int(x) for x in input().split()]
tot = sum(arr)
edges = 0
for i in range(m):
	(a, b) = map(int, input().split())
	edges += 1
q = int(input())
for i in range(q):
	query = [x for x in input().split()]
	if query[0] == '+':
		edges += 1
	elif query[0] == '-':
		edges -= 1
	else:
		ans = tot + 2 * edges - maxi
		print(ans)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
g = [0 for _ in range(n)]
s1 = sum(arr)
for i in range(m):
	(x, y) = map(int, input().split())
	g[min(x, y) - 1] += 1
s2 = sum([2 * g[i] - (n - i - 1) for i in range(n)])
t = int(input())
for _ in range(t):
	q = input().split()
	ans = 0
	if q[0] == '?':
		print(s2 + s1)
	elif q[0] == '+':
		(x, y) = (int(q[1]) - 1, int(q[2]) - 1)
		i = min(x, y)
		s2 -= 2 * g[i] - (n - i - 1)
		g[i] += 1
		s2 += 2 * g[i] - (n - i - 1)
	else:
		(x, y) = (int(q[1]) - 1, int(q[2]) - 1)
		i = min(x, y)
		s2 -= 2 * g[i] - (n - i - 1)
		g[i] -= 1
		s2 += 2 * g[i] - (n - i - 1)


def main():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr)
	for edges in range(m):
		(a, b) = map(int, input().split())
	pre = n * (n - 1) // 2
	ans = s - pre
	q = int(input())
	for i in range(q):
		que = list(map(str, input().split()))
		if que[0] == '?':
			print(ans + 2 * m)
		elif que[0] == '-':
			m -= 1
		elif que[0] == '+':
			m += 1
main()


(N, M) = list(map(int, input().split()))
a = list(map(int, input().split()))
answer = sum(a) - N * (N - 1) // 2
for i in range(M):
	e = input()
Q = int(input())
edges = M
for i in range(Q):
	q = input().split()
	if q[0] == '+':
		edges += 1
	elif q[0] == '-':
		edges -= 1
	else:
		print(answer + 2 * edges)


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(m):
	input()
total_price = sum(A) - n * (n - 1) // 2 + 2 * m
q = int(input())
for _ in range(q):
	query = input()
	if query[0] == '+':
		total_price += 2
	elif query[0] == '-':
		total_price -= 2
	else:
		print(total_price)


import sys
input = sys.stdin.readline

def testcase():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	price = sum(A)
	conn = [0] * n
	for i in range(m):
		(p, q) = map(int, input().split())
		conn[p - 1] += 1
		conn[q - 1] += 1
	Q = int(input())
	for i in range(Q):
		q = input().split()
		if q[0] == '?':
			print(price + m + m - n * (n - 1) // 2)
		elif q[0] == '+':
			m += 1
		elif q[0] == '-':
			m -= 1
testcase()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
s = sum(l)
for i in range(m):
	(u, v) = map(int, input().split())
q = int(input())
temp = m
t2 = n * (n - 1) // 2
while q:
	q -= 1
	x = input()
	if x[0] == '?':
		print(s + 2 * temp - t2)
	elif x[0] == '-':
		temp -= 1
	else:
		temp += 1


from collections import Counter
from sys import *
from collections import defaultdict as dd
from math import *

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

def vinp():
	return map(int, stdin.readline().strip().split())

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

def sinp(n=1):
	if n == 1:
		return stdin.readline().strip()
	elif n == 2:
		return list(stdin.readline().strip())
	else:
		return list(stdin.readline().strip().split())

def pr(*x, end='\n'):
	print(*x, end=end)

def mod(f, val=1000000007):
	return f % val

def csort(c):
	sorted(c.items(), key=lambda pair: pair[1], reverse=True)

def indc(l, n):
	c = {}
	for i in range(n):
		c[l[i]] = c.get(l[i], []) + [i + 1]
	return c
(n, m) = vinp()
l = linp()
summ = sum(l)
for i in range(m):
	(u, v) = vinp()
q = inp()
temp = m
su = n * (n - 1) // 2
while q:
	q -= 1
	s = sinp()
	if s[0] == '?':
		pr(summ + temp + temp - su)
	elif s[0] == '+':
		temp += 1
	else:
		temp -= 1


(N, M) = map(int, input().split())
arr = list(map(int, input().split()))
sm = sum(arr)
for i in range(M):
	(q, v) = map(int, input().split())
Q = int(input())
cnt = M
tot = N * (N - 1) // 2
while Q:
	q = list(map(str, input().split()))
	if q[0] == '?':
		ad = tot - cnt
		print(sm + (cnt - ad))
	elif q[0] == '+':
		cnt += 1
	else:
		cnt -= 1
	Q -= 1


nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def fn(x):
	return x * (x + 1) >> 1
for _ in range(1):
	(n, eg) = lst()
	price = lst()
	sm_p = sum(price)
	sm_d = eg
	cc = fn(n - 1)
	for i in range(eg):
		(u, v) = lst()
	for i in range(nmbr()):
		s = input()
		if s[0] == '?':
			print(sm_p + 2 * sm_d - n * (n - 1) + cc)
		elif s[0] == '+':
			sm_d += 1
		else:
			sm_d -= 1


(n, m) = map(int, input().split())
arr = [int(x) for x in input().split()]
dp = [0 for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	dp[a] = dp[a] + 1
	dp[b] = dp[b] + 1
res = sum(arr)
neb = sum(dp)
tot = n * (n - 1)
q = int(input())
for i in range(q):
	l = [x for x in input().split()]
	if l[0] == '?':
		print(res + neb // 2 - (tot - neb) // 2)
	elif l[0] == '+':
		neb = neb + 2
	else:
		neb = neb - 2


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
(n, m) = M()
a = L()
adj = {i + 1: [] for i in range(n)}
adj2 = {i + 1: 0 for i in range(n)}
for i in range(m):
	(x, y) = M()
	adj[x].append(y)
	adj[y].append(x)
	adj2[x] += 1
	adj2[y] += 1
ans = sum(a)
var = n
for i in adj:
	ans += adj2[i] - (var - 1 - adj2[i])
	for j in adj[i]:
		adj2[j] -= 1
	var -= 1
q = I()
for i in range(q):
	s = S().split()
	if s[0] == '+':
		ans += 2
		adj2[int(s[1])] += 1
		adj2[int(s[2])] += 1
	elif s[0] == '-':
		ans -= 2
		adj2[int(s[1])] -= 1
		adj2[int(s[2])] -= 1
	else:
		print(ans)


(N, M) = map(int, input().split())
arr = list(map(int, input().split()))
_sum = sum(arr) - sum([i + 1 for i in range(N - 1)])
for _ in range(M):
	_ = input()
Q = int(input())
for _ in range(Q):
	query = input().split()
	if query[0] == '?':
		print(_sum + M * 2)
	elif query[0] == '+':
		M += 1
	else:
		M -= 1


(N, M) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
graph = [[] for theta in range(N)]
for i in range(M):
	(u, v) = map(int, input().split(' '))
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
val = 0
for theta in range(N):
	val += A[theta] - theta
	for alpha in graph[theta]:
		A[alpha] += 2
Q = int(input())
for omega in range(Q):
	query = str(input())
	if query[0] == '+':
		val += 2
	elif query[0] == '-':
		val -= 2
	elif query[0] == '?':
		print(val)


t = 1
for i in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	adj = [0 for i in range(n)]
	sm = 0
	cnt = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		if u < v:
			adj[u - 1] += 1
		else:
			adj[v - 1] += 1
	for i in range(n):
		sm += arr[i]
		sm += adj[i]
		sm -= n - 1 - i - adj[i]
	q = int(input())
	for i in range(q):
		a = list(map(str, input().split()))
		if len(a) == 1:
			print(sm + cnt)
		elif a[0] == '+':
			cnt += 2
		else:
			cnt -= 2