m302. 12428 - Enemy at the Gates
Tags :
Accepted rate : 21人/26人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-10-12 15:41

Content

有一個叫做「位元國」的王國有麻煩了。敵人正處心積慮的要攻擊他。

敵人知道位元國有 N 個城市和 M 條道路(雙向的),並且從任何一個城市都可以透過道路到達另外的任何一個城市。他們也知道任兩個城市之間最多只會有一條道路直接相連。但是他們不知道哪一條道路連接哪兩個城市。

敵人計畫要摧毀位元國所有的「關鍵」道路。所謂「關鍵」道路指的是假如某條道路被摧毀後,位元國的城市會被分成不再相連的2個部分。例如道路圖:A─B─C ,B─C之間的道路是關鍵的,因為此道路被摧毀後B就不能到C了。

而 a-b-c 道路圖中,B─C之間的道路不是關鍵的,因為即使此道路被摧毀後,B仍然可以透過 B ─> A ─> C而到達C。

請問敵人根據所知道位元國的資訊,位元國中最多有幾條道路是關鍵的?

Input

輸入的第一列有一個整數T代表以下有幾組測試資料。

每組測試資料一列,含有 2 個整數 N, M ( 2<= N <= 105, N-1 <= M <= N(N-1)/2  ),代表位元國的城市數目以及道路數目。

Output

對每組測試資料輸出一列 ,輸出位元國中最多有幾條道路是關鍵的。

Sample Input #1
3
4 4
4 3
7 12
Sample Output #1
1
3
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :

前2組範例測資說明:

example1

Tags:
出處:
UVa [管理者: yatsen (愛情少校) ]

Status Forum 排行

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