在计算机的图论中，树是由编号1到N的N个节点组成，除了根节点，每个节点都有一个“父节点”。例如下面是一个5个节点的树。

image.png

其中，2 、5号节点的父节点是4号节点，3、4号节点的父节点是1号节点， 1号节点是根节点，没有父节点。

这棵树的输入格式可以为：

共若干行：每行2个整数a,b，若a和b在同一颗树，输出0。否则，a所在的树的根连接到b所在的根，合并为一颗树，输出合并后树的高度。上图的树输入数据可以为：

2 4

5 4

3 1

2 3

图论中，还有森林概念，森林由多棵树组成。

现在每次加一个关系(a,b)后，输出相应的结果。本样例输出2 2 2 3

输入格式

第1行：2个正整数N，和M，分别表示节点数，和边数，范围在[1,1000000]。

第2到M+1行：每行2个整数a,b。

【提示】数据比较大，需要使用scanf,printf。

输出格式

M个数，表示每次加一个边(a,b)后，如果a和b不在同一棵树输出合并后的树高，否则输出0。

输入/输出例子1 输入：

10 7

10 9

2 8

6 6

1 5

5 4

10 2

1 2

输出：

2 2 0 2 3 3 4