Konrad and Company Evaluation
Contest: Dasha Code Championship - SPb Finals Round (only for onsite-finalists)
Difficulty rating: 2400
Tags: graphs

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 format:
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 format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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.

Example input:
4 5
1 2
2 4
1 3
3 4
2 3
2
2
3

Example output:
4
3
2

Example input:
3 3
1 2
2 3
1 3
5
1
2
2
1
3

Example output:
1
1
1
1
1
1

Editorial:
Let's imagine that the graph is directed as in the sample explanation (and edge $$$u\to v$$$ exists if $$$u$$$ brags to $$$v$$$). We have to deal with two kinds of queries:
• Count the number of three-vertex directed paths.
• Change the direction of a single edge in the graph.
If we remember indegrees $$$\mathrm{indeg}$$$ and outdegrees $$$\mathrm{outdeg}$$$ for each vertex, then we can see that the result for the first query is $$$\sum_{v} \mathrm{indeg}(v) \cdot \mathrm{outdeg}(v)$$$. It's also easy to maintain the in- and outdegrees for each vertex when updating the graph using the second query.
Let's get back to the original problem. If a person $$$v$$$ becomes the best-paid employee in the company, we can model it as taking all the edges ending at $$$v$$$, and reversing their direction.
It turns out that throughout the whole simulation, this edge-reversal won't happen too many times! Let's sort the vertices from left to right by their degree in the decreasing order. It now turns out that each vertex is adjacent with at most $$$\sqrt{2m}$$$ vertices to its left: if there were more, it would mean that there exist more that $$$\sqrt{2m}$$$ vertices with their degrees larger than $$$\sqrt{2m}$$$. It would mean that the sum of degrees of all the vertices in the graph is more than $$$\sqrt{2m} \cdot \sqrt{2m} = 2m$$$ — a contradiction.
Define the potential of the graph as the number of edges which point from left to right. If we revise the salary for employee $$$v$$$, we might need to flip many edges, but at most $$$\sqrt{2m}$$$ new edges will start pointing from left to right. The remaining edges incident to $$$v$$$ will now point from right to left. Therefore, we do the number of swaps proportional to the change of the potential, and the potential at each query can increase at most by $$$\sqrt{2m}$$$. The potential at the beginning could be as high as $$$m$$$, and therefore the total number of swaps throughout the algorithm is at most $$$m + q\sqrt{2m}$$$.
The algorithm can be therefore implemented in $$$O(n + m + q\sqrt{m})$$$ time. Note that we should store the adjacency list of the directed graph in vectors — when we revise the salary of employee $$$v$$$, we should process all edges entering $$$v$$$ and simply clear the corresponding vector. Storing the graph in sets or hashsets has worse complexity or a huge constant factor and will likely time out.