G. Guessing Two Steps into the Multiverse
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Stephen is aware of the existence of n different universes. Every minute, a new one-way portal between two universes is discovered.

Stephen is interested in determining the number of ways he could travel from one universe to another one by going through exactly two known portals at any point in time. He is also interested in identifying the maximum number of additional travel paths between any two universes, utilizing precisely two portals, that could possibly emerge with the introduction of a single new portal the next minute. At minute zero, there are no known portals. Also, a portal may be used more than once.

You and your friend Ned have offered to write a program that can perform these calculations. Stephen feels weird about it, since he is only used to work with magic, but he will allow it.

Input

The first line of the input contains two space separated integers $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of known universes and the number of minutes where new portals will be discovered.

After that, $$$t$$$ lines follow. The $$$i$$$-th line $$$(1 \leq i \leq t)$$$ contain two space separated integers $$$u$$$ and $$$v$$$ $$$(1 \leq u,v \leq n)$$$ that indicate that in the $$$i$$$-th minute, a one-way portal from the $$$u$$$-universe to the $$$v$$$-universe was discovered.

Output

For each minute $$$i = 1, 2, \ldots, t$$$ output a line with two space separated integers. The first integer in each line should be the updated number of ways of reaching one universe from another by using exactly two portals in the $$$i$$$-th minute. The second one should be the maximum additional number of ways that could be discovered in the $$$(i+1)$$$-th minute.

Examples
Input
4 6
1 2
2 1
1 1
2 2
3 3
4 4
Output
0 2
2 3
5 5
8 5
9 5
10 5
Input
1 3
1 1
1 1
1 1
Output
1 3
4 5
9 7