Why Hoban-woo Was Late to School 4

Interview

Time limit1sMemory limit1024 MB

Summary

Given N king slimes and M items, report the total slime count after each item, where merging groups of sizes s and t adds s+t-1 mini slimes.

Level: Medium4 of 10
Topics: Union-find, Implementation
Solved: No attempts yet

Problem

In fact, ever since Hoban-woo arrived in the other world, his adventure has been broadcast from Earth on the live streaming platform Twitch.

The stream currently shows Hoban-woo trying to explore a dungeon with $N$ king slimes. Every king slime belongs to a different slime group, and they are numbered from $1$ to $N$ .

Sangho, the only viewer of the stream, will spin the TWIP slot machine $M$ times and try to merge slime groups before Hoban-woo explores the dungeon.

Each spin produces an item with a pair of positive integers $a, b$ satisfying $1 \le a < b \le N$ . The item is stored in the inventory and can be used to merge slime groups.

By consuming an item with $a, b$ written on it, the group containing king slime $a$ and the group containing king slime $b$ can be merged. If king slimes $a$ and $b$ already belong to the same group, nothing is merged. When two groups merge, $(\text{number of king slimes in the merged group} - 1)$ mini slimes are created.

Sangho wants to know how many slimes (king slimes and mini slimes) can be created in the dungeon depending on the number of spins. As the streamer, let us give the answer to Sangho, the only viewer.

Input

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

From the second line onward, each of the next $M$ lines contains a pair of positive integers $a, b$ from an item obtained from the slot machine, separated by a space. ( $1 \le a < b \le N$ )

Output

Print $M$ lines. On line $i$ , print the maximum possible number of slimes in the dungeon when all items obtained from the first $i$ spins are used.

Hint

Since the input and output are large, fast I/O is recommended. Fast I/O methods for common languages are below.

C++: If you use cin and cout, you must call cin.tie(nullptr); ios::sync_with_stdio(false); once before any I/O. When starting a new line, use '\n' instead of endl.
Java: You must use BufferedReader and BufferedWriter.
Python3, PyPy3: You must use sys.stdin.readline().rstrip() instead of input().

Examples2

Example 1
Input
```
4 4
1 2
3 4
2 3
1 4
```
Expected output
```
5
6
10
10
```

Example 2

Input

Expected output