User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

57.9% (11/19)

Description

在一座城市中,有許許多多的基地台,每個基地台負責不同的事務,
而這些基地台會利用線纜連接起來以傳輸資料,達成協同工作的目的,
如果兩個基地台透過直接或間接的方式連接起來,
則這兩個基地台可以互相傳輸資料。
例如:$1$ 與 $2$ 相連、$2$ 與 $3$ 相連,則 $1,2,3$ 可以互相傳輸資料。

因為基地台使用無線網路的技術,因此會需要調整好無線電波的頻率,
才能使得基地台之間不會互相干擾。
我們定義若兩個基地台之間被一條線纜連起來,
且中間沒有經過其他基地台者,稱之為相鄰基地台。
如果兩個相鄰基地台使用相同頻率的電波時,會造成訊號的干擾,
進而影響到基地台的正常運作,
可能會導致直播沒聲音,畫面中斷等等的問題,
嚴重者可能導致遠距教學的學生無法上課。
為了避免上述問題,因此相鄰的基地台必須使用不同頻率的電波才可以。
身為基地台工程師的你,需要計算出要使用多少種不同頻率的電波,
才能讓所有基地台都正常運作。

保證任兩個不同的基地台都有辦法互相傳輸資料,
且兩基地台之間傳輸資料的路徑唯一。

Input Format

第一行輸入兩個整數 $N,M$ 分別代表基地台數量與線纜數量。
接下來 $M$ 行,每行有兩個數字 $a,b\ (a\neq b)$,代表編號 $a$ 的基地台與編號 $b$ 的基地台透過一條線纜連接起來。

  • $1\leq N\leq2\times10^6$
  • $0\leq M\leq4\times10^6$
  • $1\leq a,b\leq N$

Output Format

請輸出一個數字,代表讓所有基地台能正常運作下,最少需要使用多少種不同的頻率。

Sample Input 1

4 3
3 4
2 1
2 3

Sample Output 1

2

Sample Input 2

5 4
1 2
1 3
1 4
1 5

Sample Output 2

2

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~22 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1