TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

91.3% (84/92)

Submission's AC Ratio

45.6% (130/285)

Tags

Description

骨幹網路是網際網路中重要的基礎設施。骨幹網路由多台伺服器組成,彼此間以高速網路連結;其他電腦與裝置,則透過骨幹網路連線到網際網路上。機關、學校、公司與資料中心也經常透過建置自己的骨幹網路,來提供內部與外部的網路服務。
骨幹網路中的伺服器通常透過不只一條的實體連線相互連結,提供妥善的分流與備援。確保每條連線的品質,就是確保骨幹網路穩定的基本方法,然而有效率的測試所有連線可能是相當艱鉅的任務。假設每條直接連線都是雙向的,考慮以下的簡單方法:「每台伺服器都有自己的唯一 ID 識別碼。每台伺服器查看所有與自己直接連線的伺服器ID,如對方的ID 比自己的ID 大,則ID 較小的伺服器負責對此連線進行測試。」
如此一來,每條直接連線都會被測試恰好一次。然而 ID 較小又擁有較多直接連線的伺服器可能得負擔較多的測試,會導致測試工作的分配並不是很平均。我們能靠重新分配伺服器的 ID,以減少(最小化)伺服器最大的負擔。例如以下這張網路:

需要的測試如下:
伺服器 0 → {1, 4, 5}
伺服器 1 → {2, 5}
伺服器 2 → {3, 5}
伺服器 3 → {4}
伺服器 4 → {5,6}
伺服器 5 → {}
伺服器 6 → {}
伺服器0 最多需要 3 次測試。
若 ID 經過適當地重新分配後:

需要的測試如下:
伺服器 0 → {4}
伺服器 1 → {2, 4}
伺服器 2 → {3, 5}
伺服器 3 → {5, 6}
伺服器 4 → {5,6}
伺服器 5 → {6}
伺服器 6 → {}
伺服器1,2,3,4 最多只需要 2 次測試。
可見適當的重新分配 ID,可以使最多的連線測試次數減少。對於給定的網路關係圖,請問重新分配 ID 後,每台伺服器最多連線測試次數可以減至多少?

Input Format

輸入第一行為一個整數 T (T ≤ 10),以下包含T 組測資。
每組測資的第一行有以空白分隔的兩個整數N 與E;N 是伺服器的數量,E 表示直接連線的數量。
往後有E 行。每行包含以空白分隔的兩個整數 u 與 v (0 ≤ u,v < N),表示伺服器u與v 之間有直接連線。任一伺服器不會直接連線到自己,任兩伺服器間不會出現重複的連線,但不保證任兩伺服器之間有連通。

Output Format

每筆測資有一行輸出,輸出為空白分隔的兩個整數,分別代表重分配 ID 之前與之後的最大的連線測試數量。

Sample Input 1

1
7 10
4 6
4 0
4 5
4 3
5 0
5 1
5 2
3 2
1 0
1 2

Sample Output 1

3 2

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組15 分,N ≤ 100、E ≤ 500。
第二組18 分,N ≤ 5,000、E ≤ 80,000。
第三組20 分,N ≤ 50,000、E ≤ 200,000。
第四組22 分,N ≤ 200,000、E ≤ 400,000。
第五組25 分,N ≤ 500,000、E ≤ 800,000。

注意事項:
使用C++作答的同學,請在程式碼開頭加上#include<cstdio>,並利用scanf讀入資料。使用cin 讀入資料可能會因為讀入效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。

Problem Source

104學年度高級中學資訊學科能力競賽決賽程式設計試題第五題
Set by Paupière

Subtasks

No. Testdata Range Score
1 0 15
2 1 18
3 2 20
4 3 22
5 4 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 8000 131072 262144 1
1 8000 131072 262144 2
2 8000 131072 262144 3
3 8000 131072 262144 4
4 9500 131072 262144 5