You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1676 题。

题目描述

有 $n$ 个城市，初始时城市之间没有任何道路。然而，每天都会修建一条新的道路，最终总共有 $m$ 条道路。

一个 连通分量 是指一组城市，其中任意两座城市之间都有一条通过道路相通的路径。在每一天结束时，你需要找出当前的连通分量数量以及最大的连通分量的大小。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示城市的数量和道路的数量。城市编号为 $1,2,…,n$。

接下来有 $m$ 行，每行描述一条新的道路。每行包含两个整数 $a$ 和 $b$：表示在城市 $a$ 和城市 $b$ 之间修建了一条新的道路。

假设每条道路都连接两座不同的城市。

输出格式

输出 $m$ 行：每行表示在每一天结束时，当前的连通分量数量以及最大连通分量的大小。

样例

5 3
1 2
1 3
4 5

4 2
3 3
2 3

说明/提示

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2 \cdot 10^5$

$1 \leq a, b \leq n$。