在一座城市中,有許許多多的基地台,每個基地台負責不同的事務,
而這些基地台會利用線纜連接起來以傳輸資料,達成協同工作的目的,
如果兩個基地台透過直接或間接的方式連接起來,
則這兩個基地台可以互相傳輸資料。
例如:$1$ 與 $2$ 相連、$2$ 與 $3$ 相連,則 $1,2,3$ 可以互相傳輸資料。
因為基地台使用無線網路的技術,因此會需要調整好無線電波的頻率,
才能使得基地台之間不會互相干擾。
我們定義若兩個基地台之間被一條線纜連起來,
且中間沒有經過其他基地台者,稱之為相鄰基地台。
如果兩個相鄰基地台使用相同頻率的電波時,會造成訊號的干擾,
進而影響到基地台的正常運作,
可能會導致直播沒聲音,畫面中斷等等的問題,
嚴重者可能導致遠距教學的學生無法上課。
為了避免上述問題,因此相鄰的基地台必須使用不同頻率的電波才可以。
身為基地台工程師的你,需要計算出要使用多少種不同頻率的電波,
才能讓所有基地台都正常運作。
保證任兩個不同的基地台都有辦法互相傳輸資料,
且兩基地台之間傳輸資料的路徑唯一。
第一行輸入兩個整數 $N,M$ 分別代表基地台數量與線纜數量。
接下來 $M$ 行,每行有兩個數字 $a,b\ (a\neq b)$,代表編號 $a$ 的基地台與編號 $b$ 的基地台透過一條線纜連接起來。
請輸出一個數字,代表讓所有基地台能正常運作下,最少需要使用多少種不同的頻率。
No. | Testdata Range | Score |
---|---|---|
1 | 0~22 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 |