Amy asks Mr. B problem E. Please help Mr. B to solve the following problem.
There are n people, who don't know each other at the beginning.
There are m turns. In each turn, 2 of them will make friends with each other.
The friend relation is mutual and transitive.
If A is a friend of B, then B is also a friend of A.
For example, if A is a friend of B, B is a friend of C, then A and C are friends.
At the beginning and after each turn, please calculate the number of ways to select four people from, such that any two of these four are not friends.
输入描述:
The first line contains two integers, n and m (n <= 100000, m <= 200000), which are the number of people, and the number of turns.
In the following m lines, the i-th line contains two integers x and y ( 1 <= x <= n, 1 <= y <= n, x ≠ y), which means the x-th person and the y-th person make friends in the i-th turn.
The x-th person and y-th person might make friends in several turns.
输出描述:
Output m+1 lines, each line contains an integer, which is the number of quadruples.
Output at the beginning and after each turn, so there are m+1 lines.
示例1
输入
复制
6 6
1 2
3 4
4 5
3 5
3 6
2 4