UOJ Logo

NOI.AC

1S 512MB

#52. computer

统计

题目描述

小 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$。