题目描述

有 $n$ 个人，起初任意两人都互不认识。两个人之间存在联系，当且仅当他们相识，或能通过若干位相识的人间接联系。

依次给出 $d$ 个条件。第 $i$ 个条件要求第 $x_i$ 个人与第 $y_i$ 个人最终存在联系。对每个 $i$，你需要考虑一种独立的安排：恰好进行 $i$ 次相互介绍，并满足前 $i$ 个条件。

在满足条件的前提下，求某个人最多能拥有多少位熟人（直接或间接联系到的其他人）。输出每个 $i$ 的答案。

输入格式

第一行输入两个整数 $n,d$（$2 \le n \le 1000$，$1 \le d \le n-1$），分别表示人数和条件数量。

接下来 $d$ 行，第 $i$ 行输入两个整数 $x_i,y_i$（$1 \le x_i,y_i \le n$，$x_i \ne y_i$），表示第 $i$ 个条件。

输出格式

输出 $d$ 行，第 $i$ 行输出满足前 $i$ 个条件且恰好进行了 $i$ 次介绍时，某个人最多可以拥有的熟人数。

样例

样例 1

输入：

7 6
1 2
3 4
2 4
7 6
6 5
1 7

输出：

1
1
3
3
3
6

样例 2

输入：

10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4

输出：

1
2
3
4
5
5
6
8