L. Proposition Composition
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

These is an undirected connected graph $$$G$$$ with $$$n$$$ vertices and $$$(n-1)$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$ (both inclusive) and the $$$i$$$-th edge connects vertices $$$i$$$ and $$$(i + 1)$$$.

There will be $$$m$$$ extra edges added to this graph. Each addition is permanent. After each edge is added, output the number of ways to choose two edges $$$e$$$ and $$$f$$$ from the graph such that if both edges $$$e$$$ and $$$f$$$ are removed from the graph, the graph will become disconnected (that is, the graph will have at least two connected components).

Note that first choosing $$$e$$$ then choosing $$$f$$$ is considered the same way as first choosing $$$f$$$ then choosing $$$e$$$.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2.5\times 10^5$$$) indicating the size of the graph and the number of extra edges.

For the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) indicating the $$$i$$$-th extra edge connects vertices $$$u_i$$$ and $$$v_i$$$.

It's guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ over all test cases will exceed $$$2.5 \times 10^5$$$.

Output

For each test case output $$$m$$$ lines where the $$$i$$$-th line contains the answer after the $$$i$$$-th extra edge is added.

Example
Input
3
4 3
2 4
4 2
3 3
7 3
3 4
1 2
1 7
6 4
1 3
4 6
2 5
3 4
Output
6
5
6
21
24
10
15
12
3
2
Note

We explain the first sample test case as follows.

After adding the first extra edge, removing any two edges will make the graph disconnected. So the answer is $$$6$$$.

After adding the second extra edge, we can choose original edge $$$1$$$ and any other edge, or choose original edge $$$2$$$ and original edge $$$3$$$. The answer is $$$4 + 1 = 5$$$.

After adding the third extra edge, we can choose original edge $$$1$$$ and any other edge, or choose original edge $$$2$$$ and original edge $$$3$$$. The answer is $$$5 + 1 = 6$$$.