#T2105. 道路建设(Road Construction)

道路建设(Road Construction)

链接: https://cses.fi/problemset/task/1676

板块: Graph Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

有 nn 座城市,起初它们之间没有道路。不过,每天都会新建一条道路,最终共有 mm 条道路。

一个连通块是一组城市,其中任意两座城市之间都能通过道路互通。每天结束后,你的任务是求出连通块的数量以及最大连通块的大小。

输入

第一行输入包含两个整数 nn 和 mm:城市数量和道路数量。城市编号为 1,2,…,n1,2,\dots,n。

接着有 mm 行描述新建的道路。每行包含两个整数 aa 和 bb:在城市 aa 和 bb 之间新建一条道路。

你可以假设每条道路都建在两条不同的城市之间。

输出

输出 mm 行:每天之后的所需信息。

数据范围

1≤n≤1051 \le n \le 10^5 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5 1≤a,b≤n1 \le a,b \le n

样例输入

5 3
1 2
1 3
4 5

样例输出

4 2
3 3
2 3