NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
3 . 網際網鹿
TopCoder
Tags
Description
透過強大的網際網鹿，鹿乃子乃子可以收集到虎視虎子的各種情報
在虎視虎子王決定戰結束後，鹿乃子乃子打算重新安排網際網鹿的運作結構。
網際網鹿由 $N$ 臺「鹿岳」超級電腦以及 $M$ 條纜線所組成，電腦以 $1$ 到 $N$ 的整數編號。每一條纜線皆連接著兩臺相異的電腦，並且任兩臺電腦之間至多只會有一條纜線連接，透過纜線連接的兩臺電腦可以互相傳送封包。
鹿乃子乃子打算將所有電腦分配至 $3$ 個叢集，每一臺電腦恰屬於其中一個叢集，並且每個叢集至少包含一臺電腦。由於同一個叢集之間的電腦有另外的方式能進行更快速且安全的傳輸方法，在決定完叢集的分配方式後，如果一條纜線兩端的電腦屬於同一個叢集，則鹿乃子乃子會移除這條纜線。
當一臺電腦在不經過重複的纜線的情況下能將封包傳送回自己，則此時我們稱纜線形成了「迴鹿」。存在迴鹿的架構可能造成廣播風暴，影響封包傳輸，因此鹿乃子乃子希望安排的叢集不要有任何迴鹿產生。
由於現在鹿岳電腦正在維護當中，請你寫一支程式幫助鹿乃子乃子將所有電腦分配至 $3$ 個叢集，並避免產生任何的迴鹿。
Input Format
輸入的第一行為一整數 $T$，表示測試資料的數量。
每一筆測試資料第一行包含兩個整數 $N, M$。接下來 $M$ 行，每行包含兩個整數 $a_i, b_i$，表示第 $i$ 條纜線連接第 $a_i$ 臺和第 $b_i$ 臺電腦。
- $1 \le T \le 8 \times 10^ 4$
- $3 \le N \le 8 \times 10^ 4$
- $0 \le M \le \max(2N-1, 2.5N-6, 3N-10)$
- $1 \le a_i, b_i \le N$
- $a_i \ne b_i$
- $(a_i, b_i) \ne (a_j, b_j) \land (a_i, b_i) \ne (b_j, a_j), \forall i \ne j$
- 保證測試資料中 $N$ 的總和不超過 $8 \times 10^ 4$
Output Format
對於每一筆測試資料，如果不存在分配叢集的方式，請輸出一行 -1；否則，請輸出一行包含一長度為 $N$ 的字串，字串的第 $i$ 個字元必須要是 1、2、或 3，表示第 $i$ 臺電腦所在的叢集。
如果有多種可能的輸出，你可以輸出任意一種。
- 每個叢集中至少要有一臺電腦
- 所有電腦必須恰好在一個叢集中
Sample Input 1
1
5 6
1 2
2 3
3 4
4 5
5 3
4 2
5 6
1 2
2 3
3 4
4 5
5 3
4 2
Sample Output 1
23111
Sample Input 2
2
5 4
1 2
1 3
3 4
3 5
5 4
1 2
2 3
1 3
4 5
5 4
1 2
1 3
3 4
3 5
5 4
1 2
2 3
1 3
4 5
Sample Output 2
11233
11123
11123
Sample Input 3
2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 5
1 2
1 4
2 3
2 4
3 4
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 5
1 2
1 4
2 3
2 4
3 4
Sample Output 3
-1
-1
-1
Hints
第一筆範例測資中，叢集的分配以及移除纜線後的網際網鹿配置如下，其中同一種顏色的圓圈表示在同一個叢集中的電腦。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 3~42 | $M \leq 2N-4$ | 0.1 |
| 3 | 3~60 | $M \leq 2N-3$ | 4.9 |
| 4 | 0~79 | $M \leq 2N-1$ | 5 |
| 5 | 0~114, 174 | $M \leq \max(2N-1, 2.5N-6)$ | 39 |
| 6 | 0~174 | 無額外限制 | 51 |