Link Cut Digraph

Time limit3sMemory limit512 MB

Summary

Edges of a directed graph arrive one at a time, and after each insertion the task is to count pairs of vertices that are mutually reachable. Up to 1e5 vertices and 2.5e5 edges.

Level: Hard10 of 10
Topics: Graph, Divide and conquer, Union-find
Solved: No attempts yet

Problem

You are given a graph with $n$ vertices and no edges at first. There are $m$ operations. Each operation adds a given directed edge to the graph, then outputs the number of pairs $(u, v)$ ( $1 \leq u < v \leq n$ ) such that $u$ is reachable from $v$ and $v$ is reachable from $u$ .

Can you implement the algorithm from the paper in an ICPC contest?

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 10^5$ , $1 \leq m \leq 2.5 \cdot 10^5$ ). Each of the following $m$ lines contains two integers $u$ and $v$ ( $1 \leq u, v \leq n$ ) indicating a newly added directed edge. Parallel edges and self-loops are allowed.

Output

Output $m$ integers, one per line: the number of pairs after adding each given edge.

Examples1

Example 1

Input

Expected output