AT_ttpc2022_h Colorful Graph

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

$ \max\{c_1, …, c_N\} $ が最小になる塗り方を以下の形式で出力せよ。 > $ c_1 $ $ c_2 $ $ \cdots $ $ c_N $

### 注意 この問題のメモリ制限は 256 MB です。 ### Sample Explanation 1 頂点 $ 2 → 5 → 1 → 4 $ のパスがあるので、頂点 $ 1, 2, 4, 5 $ を同じ色に塗ることができます。 頂点 $ 3, 4 $ 間にはパスが存在しないので、 $ 2 $ 色以上は必要です。 ### Constraints - 入力はすべて整数 - $ 1