Ever since Hobanwoo arrived in the other world, his journey has been broadcast live on Earth via the streaming platform Twitch.

Currently, the broadcast shows Hobanwoo exploring a dungeon where $N$ slimes, each of size 1 and numbered from $1$ to $N$, respawn every day.

Sangho, the only viewer of the broadcast, intends to use the "Twip" slot machine once every day for $M$ days to merge the slimes before Hobanwoo arrives.

When the slot machine is spun, a pair of positive integers $a$ and $b$ such that $1 \le a < b \le N$ is generated, which is then stored in the inventory and can be used to merge slimes each day.

When a pair of positive integers $a$ and $b$ is used, the slime group containing slime $a$ and the slime group containing slime $b$ are merged. If slime $a$ and slime $b$ already belong to the same slime group, they are not merged.

The size of the merged slime is defined as: $(\text{sum of the sizes of the two merged slimes}) + (\text{number of slimes belonging to the merged slime among the } N \text{ slimes})$.

Sangho is curious about how large the sum of the sizes of all slimes in the dungeon can be each day. As a streamer, let's provide the answer to Sangho, your only viewer!

Input

The first line contains the number of slimes $N$ and the number of days $M$ that Sangho spins the slot machine, separated by a space. $(2 \le N \le 200\,000, 1 \le M \le 300\,000)$

From the second line, $M$ lines follow, each containing a pair of positive integers $a$ and $b$ generated by the slot machine each day, separated by a space. $(1 \le a < b \le N)$

Output

Output the answers over $M$ lines.

On the $i$-th line, output the maximum possible sum of the sizes of the slimes in the dungeon on the day the slot machine is spun for the $i$-th time.

Examples

Input 1

2 1
1 2

Output 1

3

Input 2

2 2
1 2
1 2

Output 2

3
3