c094. 雷達通訊 - TCFSH CIRC Judge

Content

有n顆雷達中間有m條電纜連接，任意兩顆雷達間都存在唯一一條最短路徑，每個雷達都有自己的通訊頻率。為了避免雷達間互相干擾，任兩顆相鄰的雷達需使用不同的通訊頻率。請問最少需要使用到幾種不同的頻率來進行通訊?

Input

第一行有兩個整數$N$，$M$
接下來有$M$行$x, y$，代表$x$號雷達與$y$號雷達間有一條電纜。

$1 \leq N \leq 10^5$
$ 1 \leq M \leq 10^6$
$1 \leq x,y \leq N$

Output

輸出一個整數，代表最少須用到的頻率數量。

Sample Input #1

Sample Output #1

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1K
不公開測資點#4 (10%): 1.0s , <1K
不公開測資點#5 (10%): 1.0s , <1K
不公開測資點#6 (10%): 1.0s , <1K
不公開測資點#7 (10%): 1.0s , <1K
不公開測資點#8 (10%): 1.0s , <1K
不公開測資點#9 (10%): 1.0s , <1K

Hint ：

在範例中，可以將1,4,5使用同一種頻率，2,3使用同一種頻率，最少需要2種

Tags:

2022成大程式邀請賽

出處:

2022成大程式邀請賽 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」