Electrician Master Xiao Ming is repairing an electrical box.
There are $$$n$$$ components arranged in a row in the electrical box, numbered from left to right as $$$1,2,3,\ldots,n$$$. There are also $$$m$$$ wires connecting pairs of components. The $$$i$$$-th wire ($$$1 \le i \le m$$$) connects components numbered $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \lt y_i \le n$$$), and any two components are directly connected by at most one wire, i.e., $$$\forall 1 \le i \lt j \le m$$$, $$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$. Current can flow through the wires in any direction. We refer to a wire connecting components $$$a$$$ and $$$b$$$ as an unordered pair $$$(a,b)$$$, meaning $$$(a,b)$$$ and $$$(b,a)$$$ represent the same wire.
To facilitate maintenance, the electrical box must satisfy the requirement:
no two wires intersect, i.e., $$$\forall 1 \le i \lt j \lt k \lt l \le n$$$, wires $$$(i,k)$$$ and $$$(j,l)$$$ cannot coexist.
Xiao Ming has a detection tool with four probes. When these probes are connected to four distinct components $$$i,j,k,l$$$ in sequence, if the wires $$$(i,j)$$$, $$$(j,k)$$$, and $$$(k,l)$$$ all exist, the tool can detect whether this circuit segment is functioning properly.
Xiao Ming is in a hurry to leave work, so he wants to know how many such circuit segments need to be tested. Specifically, he needs to count the number of ordered quadruples $$$(i,j,k,l)$$$ satisfying:
During the repair process, Xiao Ming will sequentially add $$$q$$$ wires. The $$$i$$$-th wire ($$$1 \le i \le q$$$) connects components $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$). As a qualified electrician, after adding each wire, the electrical box must still satisfy all the aforementioned requirements. After each addition, Xiao Ming must perform a full inspection. Therefore, he needs to determine the number of valid ordered quadruples in the initial electrical box and after each wire addition.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5 \times 10^5$$$, $$$0 \le m \le 1 \times 10^6$$$), representing the number of components and the initial number of wires.
The next $$$m$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \lt y_i \le n$$$), describing the $$$i$$$-th wire.
The following line contains an integer $$$q$$$ ($$$0 \le q \le 1 \times 10^6$$$), the number of queries.
The next $$$q$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$), describing the $$$i$$$-th wire added.
Output $$$q + 1$$$ lines. The first line indicates the number of valid ordered quadruples in the initial electrical box. The $$$(i + 1)$$$-th line ($$$1 \le i \le q$$$) indicates the count after adding the first $$$i$$$ wires.
4 31 22 33 422 41 4
2 4 12
Initially, there are two valid ordered quadruples $$$(1,2,3,4)$$$ and $$$(4,3,2,1)$$$.
After the first addition, two new quadruples $$$(1,2,4,3)$$$ and $$$(3,4,2,1)$$$ are added, totaling 4.
After the second addition, there are 12 valid ordered quadruples.
Due to the large input/output data size, please use fast I/O methods.
