NPSC 王國有 n 個城市以及 m 條道路，城市編號為 1 到 n，而一條道路連接兩個相異的城市，使得任兩個城市皆可以透過若干條道路抵達彼此。
為了交通的穩定性，NPSC 王國的道路設計還有另一個特點：對於任一條道路（假設它連接城市 x 與 y ），則如果從 x 開始經過這條道路抵達 y ，那麼至多只有一種方法可以再從 y 走回 x 而途中不經過重複的城市與道路（包含 (x, y) 這條道路）。
雖然這種道路的設計大量的減少了人們在同一些城市之間不斷繞來繞去的現象，由於 NPSC 國沒有設置良好的路標，因此還是時常發生有人迷路的事件。身為交通部部長的你，決定將所有城市分成若干類，使得每一條道路都連接兩個不同類的城市。如此一來，人們就能比較方便的確認自己行駛的方向。 當然，如果城市被分成太多類的話也會造成反效果，使得交通系統變得太複雜。
因此，你希望將城市在分成最少類的同時，也達到上述的效果。
輸入第一行有兩個非負整數 n 和 m ，分別代表城市以及道路的數量。
接著 m 行，第 i 行兩個有正整數 ui , vi ，代表第 i 條道路連接編號 ui 以及編號 vi 的城市。
1. 1 ≤ n ≤ 5 × 105
2. 1 ≤ ui , vi ≤ n
3. 保證 ui ≠ vi ，且任兩個城市之間至多只有一條道路
第一行輸出一個正整數 k，代表最少所需的城市類別。
第二行輸出 n 個介於 1 和 k 的正整數，代表城市的類別。整數之間以空格相隔，末尾換行，請勿在末尾輸出空格或其他字元。
如果有多種正確的解答，輸出任意一種都為正確。
#test input 1: 4 3 1 2 2 3 3 4 #test input 2: 4 4 1 2 2 3 3 4 4 1 #test input 3: 5 5 1 2 2 3 3 4 4 5 5 1
#test output 1: 2 1 2 1 2 #test output 2: 2 1 2 1 2 #test output 3: 3 1 2 1 2 3
graph, dfs/bfs (CF 1500)
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||