题目描述

小 S 家里有一台奇怪的计算机……

这台计算机中共有 $n$ 颗 CPU。它们之间通过 $m$ 条连接线相连，所有的 CPU 和连接线，分别用从 1 开始的连续正整数进行编号。

每一颗 CPU 上能够存储一个值。初始时，1 号 CPU 上的值为 0，而其他 CPU 的值均为 $10^9$。接下来，这台计算机的计算过程如下所述：

1. 随机选取一条连接线，设这条连接线是 $i$ 号连接线；
2. 随机选取这条线的一端，设它为 $x$ 号 CPU；
3. 设这条线的另一端为 $y$ 号 CPU；
4. 设 $t$ 为：$x$ 号 CPU 上的值与 $i$ 中较大的数；
5. 如果 $t$ 比 $y$ 号 CPU 上的值更小，则将 $y$ 号 CPU 上的值改写为 $t$。

计算机将重复上述过程，直到稳定：即无论在前两步中如何选取，都无法在最后一步改写任何 CPU 上的值。

你需要计算稳定状态下所有 CPU 上的值。如果答案不唯一，你可以输出任何一个解。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$。

接下来 $m$ 行，每行输入两个正整数。设第 $i$ 行输入的两个数为 $a_i, b_i$，则表示编号为 $i$ 的线连接了 $a_i$ 与 $b_i$ 号 CPU。

每行中，相邻的两个数之间用一个空格隔开。

输出格式

输出到标准输出。

输出 $n$ 行，每行一个整数，其中第 $j$ 行的数表示编号为 $j$ 的 CPU 在最终稳定状态下的值。

如果有多组解，你可以输出任意一组。

样例

输入

6 8
1 4
2 3
1 2
4 2
1 6
2 6
3 6
4 6

输出

0
3
3
1
1000000000
5

数据规模

对于 20% 的测试点，保证 $n, m \leq 10$。

对于 30% 的测试点，保证 $n \leq 100, m \leq 1,000$。

对于 50% 的测试点，保证 $n \leq 1,000, m \leq 10,000$。

对于 70% 的测试点，保证 $n \leq 10,000, m \leq 50,000$。

对于所有数据，保证 $n \leq 100,000, m \leq 300,000$。