有一個叫做「位元國」的王國有麻煩了。敵人正處心積慮的要攻擊他。
敵人知道位元國有 N 個城市和 M 條道路(雙向的),並且從任何一個城市都可以透過道路到達另外的任何一個城市。他們也知道任兩個城市之間最多只會有一條道路直接相連。但是他們不知道哪一條道路連接哪兩個城市。
敵人計畫要摧毀位元國所有的「關鍵」道路。所謂「關鍵」道路指的是假如某條道路被摧毀後,位元國的城市會被分成不再相連的2個部分。例如道路圖:A─B─C ,B─C之間的道路是關鍵的,因為此道路被摧毀後B就不能到C了。
而 道路圖中,B─C之間的道路不是關鍵的,因為即使此道路被摧毀後,B仍然可以透過 B ─> A ─> C而到達C。
請問敵人根據所知道位元國的資訊,位元國中最多有幾條道路是關鍵的?
輸入的第一列有一個整數T代表以下有幾組測試資料。
每組測試資料一列,含有 2 個整數 N, M ( 2<= N <= 105, N-1 <= M <= N(N-1)/2 ),代表位元國的城市數目以及道路數目。
對每組測試資料輸出一列 ,輸出位元國中最多有幾條道路是關鍵的。
3 4 4 4 3 7 12
1 3 2
前2組範例測資說明:
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|