给定一个包含 $N$ 个顶点和 $M$ 条边的连通无向图 $G$，顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $M$。

对于每个顶点 $v$，如果移除顶点 $v$ 后图不再连通，我们称 $v$ 为一个关键顶点（critical vertex）。注意，原图是否连通并不影响此定义。

对于每一条边 $i$ ($1 \le i \le M$)，请计算当移除边 $i$ 后，图 $G$ 中关键顶点的数量。注意，该移除操作仅是临时的，不会影响其他查询。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($2 \le N \le 250\,000, 1 \le M \le 1\,000\,000$)。

接下来的 $M$ 行给出图的边。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示连接顶点 $x_i$ 和 $y_i$ 的第 $i$ 条边 ($1 \le x_i, y_i \le N, x_i \neq y_i$)。图中可能存在重边。图是连通的。

输出格式

输出 $M$ 行。第 $i$ 行输出一个整数，表示移除第 $i$ 条边后，图 $G$ 中关键顶点的数量。

样例

样例输入 1

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

样例输出 1

4
2
4
4
2