割點個數

題目敘述

一個區域有 n 個城鎮，鎮與鎮之間以雙向道路相連。如果關閉某個城鎮（連同所有接到它的道路）之後，剩下的城鎮被分成的群組數比原本更多，這個城鎮就稱為要衝。原本的路網可能已經分成好幾個互不相通的群組。

請計算要衝的個數。

輸入格式

• 第一行有兩個整數 n 與 m，分別是頂點數與邊數。
• 接下來 m 行，每行兩個整數 u、v（1 ≤ u, v ≤ n，u ≠ v），表示 u 與 v 之間有一條無向邊。
• 頂點編號從 1 開始。圖不一定連通，也不會有重邊或自環。

輸出格式

輸出一個整數，表示要衝城鎮的個數。

限制

• 1 ≤ n ≤ 500
• 0 ≤ m ≤ n + ⌊ n/2 ⌋

範例

範例 1

輸入

5 4
1 2
2 3
3 4
4 5

輸出

3

說明

關閉城鎮 2、3 或 4 都會把這條鏈切成兩段。

範例 2

輸入

4 5
1 2
2 3
3 4
4 1
2 4

輸出

0

說明

每個城鎮都能繞過環或額外的道路 2-4，所以沒有要衝。

範例 3

輸入

3 2
1 2
2 3

輸出

1

說明

只有中間的城鎮 2 是要衝。

範例 4

輸入

5 3
1 2
3 4
4 5

輸出

1

說明

城鎮 1、2 自成一組，其中沒有要衝；在 3-4-5 這一組裡，只有城鎮 4 是要衝。