078 - Difference Optimization 1 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 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