← 返回题目列表

AtCoder · math_and_algorithm_bk

078. 差异优化1

中文机器翻译题面 查看原题

配点: 1000 点

注意

根据本书的版本,书中的约束可能不正确。请参阅勘误表。

对书中约束的更正 誤:1 \le A_i < B_i \le M
正:1 \le A_i < B_i \le N

問題文

ALGO 房子是 N 我们是一家人,每个人都有 它们的编号最大为 1 减去 N 。你是一个人 1 的年龄是 0 岁,还有其他人的年龄。 我知道它是一个小于或等于 0 以上 120 的整数。另外,以下 我们知道满足 M 条件。

  • 人 A_1 和人 B_1 的年龄是 0 进动或 1 进动。 请打印
  • 人 A_2 和人 B_2 的年龄是 0 进动或 1 进动。 请打印
  • :
  • 人 A_M 和人 B_M 的年龄是 0 进动或 1 进动。 请打印

人 1,2,3,\dots,N 的最大可能年龄。

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq 500000
  • 1 \leq A_i < B_i \leq N
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
:
A_M B_M

出力

N 行。 列出

i 行目 (1 \leq i \leq N) 有人 i 的最大可能年龄。


入力例 1

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

出力例 1

0
1
1
2
2
3