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.

题目背景

（题面最后提供了形式化的描述）

克露丝卡尔酱最近开始游玩“实况足球”手游，在天梯遭遇10连败之后，又不幸匹配上了臭名昭著的“倒脚狗”。只见那可憎的对手将足球从后卫传到门将，又从门将传到后卫，又从后卫传到门将······

是可忍，孰不可忍！怒不可遏的克露丝卡尔酱操纵自己的球员大举压上，向对手展开了高压逼抢。只可惜那对手发扬 Tiki-taka 战术，来回传球，把克露丝卡尔酱的上抢球员耍的团团转。

说时迟，那时快，对手见克露丝卡尔酱全军出击，后防空虚，一个大脚将皮球开到前场。对手的前锋接球长驱直入，轻松攻破了克露丝卡尔酱的大门！

克露丝卡尔酱自闭的卸载了“实况足球”，虽然过了几天又下了回来。但是在东山再起之前，她想要请教“实况足球”领域大神——你，该如何对付可恶的“倒脚狗”。

一场球赛上，对手共有 $n$ 名球员，但由于距离和技术限制，并不是任何两名球员之间都可以互相直接传球。具体来说，有且仅有 $m$ 对球员之间可以互相传球。

当对手持球时，克露丝卡尔酱可以操纵球员上抢和封堵传球路线，具体地，当 $x+1$ 名队员去高压逼抢时:

• 有 $1$ 名球员上抢，干扰持球球员。
• 其余 $x$ 名球员，每个球员会封堵至多一条传球路线。

由于没有练习过花式技巧，持球球员不会过人。因此在受到干扰后，持球球员必须立刻将球通过一条传球路线传给某个队友。

如果某一时刻，持球球员发现自己所有的传球线路都被封堵。此时上抢球员直扑右脚，持球球员丢失球权。

然而，过多的前场逼抢会快速地消耗球员体力，同时也会给防守带来隐患。因此，克露丝卡尔酱希望想知道：当对方的第 $i$ 号球员拿球时，$x$ 至少为多少，可以保证在有限的时间内抢下足球？

题目描述

一个 $n$ 个点 $m$ 条边的无向图（无重边自环），一个棋子，还有一个常数 $x$。A 和 B 玩一个游戏。

初始棋子位于 $i$ 节点，此后每一回合：

• B 选定至多 $x$ 条边删掉
• A 把棋子沿着某条边移到另一个节点
• B 把刚刚删掉的边复原

如果 A，B 都绝顶聪明，并且在有限轮中，B 可以把 A 逼入绝境（无法移动），则 B 胜利，否则 A 胜利。

对于 $i\in[1,n]$ 求 $x$ 至少为多少，B 才胜利。

输入格式

第一行包含两个整数 $n$ $(1\le n\le 10^6)$ 和 $m$ $(0\le m\le 2\times 10^6)$，表示图中的节点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ $(1\le u,v\le n)$，表示球员 $u$ 和球员 $v$ 之间可以互相传球。

保证图无重边自环。

输出格式

输出一行 $n$ 个整数，表示对 $i=1\sim n$ 的答案。

输入输出样例 #1

输入 #1

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

输出 #1

2 2 2 1 1

输入输出样例 #2

输入 #2

1 0

输出 #2

0

输入输出样例 #3

输入 #3

6 9
1 2
1 3
1 4
1 5
1 6
2 3
2 5
2 6
5 6

输出 #3

3 3 2 1 3 3

输入输出样例 #4

输入 #4

3 2
1 2
2 3

输出 #4

1 1 1