注意

この問題のメモリ制限は 256 MB です。

問題文

N 頂点 M 辺の有向グラフが与えられます。頂点には 1 から N の番号が、辺には 1 から M の番号がついています。辺 i (1 ≤ i ≤ M) は頂点 A_i から頂点 B_i に向かう辺です。

あなたは、このグラフの各頂点を色 1, …, N のいずれかで塗ります。ただし、頂点 i (1 ≤ i ≤ N) に塗る色を c_i としたとき、以下の条件を満たす必要があります。

• 任意の組 (i, j) (1 ≤ i < j ≤ N) について、c_i = c_j ならば、頂点 i から頂点 j へのパスか、頂点 j から頂点 i へのパスのいずれか (両方でもよい) が存在する。

\max\{c_1, …, c_N\} が最小になる塗り方を 1 つ構築してください。

制約

• 入力はすべて整数
• 1 ≤ N ≤ 7 \times 10^3
• 0 ≤ M ≤ 7 \times 10^3
• 1 ≤ A_i, B_i ≤ N (1 ≤ i ≤ M)
• A_i ≠ B_i (1 ≤ i ≤ M)
• (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)

入力例 1

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

出力例 1

1 1 1 2 1

頂点 2 → 5 → 1 → 4 のパスがあるので、頂点 1, 2, 4, 5 を同じ色に塗ることができます。

頂点 3, 4 間にはパスが存在しないので、2 色以上は必要です。

入力例 2

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

出力例 2

2 2 1 1 1

入力例 3

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

出力例 3

4 4 4 4 3 4 2 1