TopCoder

User's AC Ratio

71.4% (10/14)

Submission's AC Ratio

40.0% (16/40)

Description

題目在這裡

Dark Kingdom 決定以有瞬間傳送效果的黑暗傳送路徑建立新的運輸系統。這個法術有破壞地表的副作用,所以 Dark Kingdom 的法術工程師要把所有 n 個城市用環狀的路徑串接起來。

如圖,在這個傳送系統完成之後,彼得要從 3 到 2(藍色的線),雖然要傳送 5 次,但是還是比騎馬直接過去快多了,不過彼得覺得走這樣一趟就要付 5 元實在是很貴。有一天彼得在傳送的時候睡著了,他醒過來的時候剛好在 2,只是不知道已經環遊 Dark Kingdom 多少次了;但是當他要付錢離開傳送站的時候發現還是只要付 5 元!
聰明的彼得發現,進傳送站時拿的水晶,不是紀錄傳送了幾次,而是從哪個城進站。另一天彼得進入 3 的傳送站時,遇到了一個要從 1 到 4(紅線)的朋友,他就提議兩個人交換水晶,結果兩個人竟然都只要付 1 元(綠線)!

印證了自己的想法之後,彼得就開始號召了 m 個人參加這個行動,你的工作是寫一個程式,幫彼得計算他可以幫大家省多少錢。

Input Format

輸入包含多組測試資料。 第一行有兩個整數 n,m(n,m<=30000),表示有 n 個城市,城市的編號是 0~n-1,i 號城市可以傳送到 i+1 號城市(n-1 例外,傳送到 0),接下來有 m 行,每行有兩個數字,表示每個參加計畫的人的起點城市和終點城市。

Output Format

輸出彼得可以幫大家省多少錢。

Sample Input

8 3
7 3
2 5
4 0

Sample Output

8

Hints

這幾題的測試資料檔案不小,請盡量不要用cin或cout,會影響程式的執行時間。

2015/8/1 將連結的內容搬到網頁上

Problem Source

原TIOJ1130 / [KSHSVC] 雄中公假社'07 公開賽。Problem Setter:DarkKnight。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144