Konrad is a Human Relations consultant working for VoltModder, a large electrical equipment producer. Today, he has been tasked with evaluating the level of happiness in the company.

There are $n$ people working for VoltModder, numbered from $1$ to $n$. Each employee earns a different amount of money in the company — initially, the $i$-th person earns $i$ rubles per day.

On each of $q$ following days, the salaries will be revised. At the end of the $i$-th day, employee $v_i$ will start earning $n+i$ rubles per day and will become the best-paid person in the company. The employee will keep his new salary until it gets revised again.

Some pairs of people don't like each other. This creates a great psychological danger in the company. Formally, if two people $a$ and $b$ dislike each other and $a$ earns more money than $b$, employee $a$ will brag about this to $b$. A dangerous triple is a triple of three employees $a$, $b$ and $c$, such that $a$ brags to $b$, who in turn brags to $c$. If $a$ dislikes $b$, then $b$ dislikes $a$.

At the beginning of each day, Konrad needs to evaluate the number of dangerous triples in the company. Can you help him do it?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $0 \le m \le 100\,000$) — the number of employees in the company and the number of pairs of people who don't like each other. Each of the following $m$ lines contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$) denoting that employees $a_i$ and $b_i$ hate each other (that is, $a_i$ dislikes $b_i$ and $b_i$ dislikes $a_i$). Each such relationship will be mentioned exactly once.

The next line contains an integer $q$ ($0 \le q \le 100\,000$) — the number of salary revisions. The $i$-th of the following $q$ lines contains a single integer $v_i$ ($1 \le v_i \le n$) denoting that at the end of the $i$-th day, employee $v_i$ will earn the most.


-----Output-----

Output $q + 1$ integers. The $i$-th of them should contain the number of dangerous triples in the company at the beginning of the $i$-th day.


-----Examples-----
Input
4 5
1 2
2 4
1 3
3 4
2 3
2
2
3

Output
4
3
2

Input
3 3
1 2
2 3
1 3
5
1
2
2
1
3

Output
1
1
1
1
1
1



-----Note-----

Consider the first sample test. The $i$-th row in the following image shows the structure of the company at the beginning of the $i$-th day. A directed edge from $a$ to $b$ denotes that employee $a$ brags to employee $b$. The dangerous triples are marked by highlighted edges. [Image]

Source: codeforces | Difficulty: VERY_HARD
Tags: Graph algorithms

Complete search


Solutions:
import sys
(n, m) = list(map(int, sys.stdin.readline().strip().split()))
L = [0 for i in range(0, n)]
H = [[] for i in range(0, n)]
for i in range(0, m):
	(x, y) = list(map(int, sys.stdin.readline().strip().split()))
	x = x - 1
	y = y - 1
	if x > y:
		(x, y) = (y, x)
	L[y] = L[y] + 1
	H[x].append(y)
ans = 0
for i in range(0, n):
	ans = ans + L[i] * len(H[i])
print(ans)
q = int(sys.stdin.readline().strip())
for i in range(0, q):
	v = int(sys.stdin.readline().strip()) - 1
	ans = ans - L[v] * len(H[v])
	L[v] = L[v] + len(H[v])
	while len(H[v]) > 0:
		w = H[v].pop()
		H[w].append(v)
		L[w] = L[w] - 1
		ans = ans + L[w] - len(H[w]) + 1
	print(ans)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
IN = [0] * n
OUT = [0] * n
INSET = [[] for i in range(n)]
for i in range(m):
	(x, y) = sorted(map(int, input().split()))
	IN[x - 1] += 1
	OUT[y - 1] += 1
	INSET[x - 1].append(y - 1)
ANS = 0
for i in range(n):
	ANS += IN[i] * OUT[i]
print(ANS)
Q = int(input())
for i in range(Q):
	q = int(input()) - 1
	ANS -= IN[q] * OUT[q]
	OUT[q] += IN[q]
	IN[q] = 0
	for x in INSET[q]:
		INSET[x].append(q)
		ANS += (IN[x] + 1) * (OUT[x] - 1) - IN[x] * OUT[x]
		IN[x] += 1
		OUT[x] -= 1
	INSET[q] = []
	print(ANS)


(n, m) = map(int, input().split())
(out, inp) = ([0] * (n + 1), [0] * (n + 1))
inset = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	if x > y:
		z = x
		x = y
		y = z
	out[y] += 1
	inp[x] += 1
	inset[x].append(y)
q = int(input())
res = 0
for ind in range(1, n + 1):
	res += inp[ind] * out[ind]
print(res)
for i in range(q):
	best = int(input())
	res -= out[best] * inp[best]
	for pred_ind in inset[best]:
		res += -out[pred_ind] * inp[pred_ind] + (out[pred_ind] - 1) * (inp[pred_ind] + 1)
		out[pred_ind] -= 1
		inp[pred_ind] += 1
		inset[pred_ind].append(best)
	out[best] += inp[best]
	inp[best] = 0
	inset[best] = []
	print(res)