Road Construction

题目描述

有 n 个城市，起初城市之间没有道路。然而，每一天会新建一条道路，总共会建成 m 条道路。 一个连通分量是指一组城市，在这组城市中任意两座城市之间都存在一条由道路连接的路径。每一天结束后，你的任务是找出当前的连通分量数量以及最大连通分量的大小。

输入格式

第一行输入包含两个整数 n 和 m：城市数和道路数。城市编号为 1,2,$\dots$,n。 接下来有 m 行描述新建的道路。每行包含两个整数 a 和 b：在城市 a 和 b 之间新建一条道路。 你可以假设每条道路都连接两个不同的城市。

输出格式

输出 m 行：每一天结束后所需的信息。

5 3
1 2
1 3
4 5

4 2
3 3
2 3

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1676|图论

来源

CSES1676|图论