一座城市正在分阶段开放新的道路。最开始，$n$ 个地点之间互不连通；随后会按照施工完成的顺序，一条一条加入双向道路。每加入一条道路，原来分开的两个区域可能会合并成一个更大的连通区域。

刘老师希望及时掌握道路网络的变化。在每条道路加入之后，请输出当前连通块的数量，以及其中包含地点数最多的连通块大小；即使新道路连接的是原本已经连通的两个地点，也要输出这一时刻的统计结果。

输入格式

第一行输入 $n,q$，随后 $q$ 行输入关系 $a,b$。

输出格式

每次输出两个统计量。

输入 #1

4 4
1 2
2 3
1 3
3 4

输出 #1

3 2
2 3
2 3
1 4

输入 #2

2 2
1 1
1 2

输出 #2

2 1
1 2

输入 #3

5 5
1 2
3 4
2 3
4 5
1 5

输出 #3

4 2
3 2
2 4
1 5
1 5

数据范围与约定

• 1 ≤ $n$,$q$ ≤ 200000