Problem : 96 - Teleporter

Problem Statistics

Solved Member: 13　　Submission: 50　　User Tried: 13

Statement:

雖然你可能這樣想，不過這題跟她一點關係都沒有。

兔子王統治了整個銀河系！他擁有了 n 個行星，分別由 1 標號到 n 。
兔子國王透過瞬間移動的方式來在皇宮以及自己家之間移動，編號 1 的星球為兔王的皇宮，編號 2 的星球為他的家，每天，兔王透過他專屬的瞬間移動裝置來移動，傳送需要花費250分鐘的時間(四小時多)。

由於科技的發達，傳送裝置也如同鐵路一般，開始在民間盛行；甚至超越了以前的技術。每一對傳送裝置雙向連接著兩個星球，並且在兩個星球之間旅行只需要花費 1 個小時整。兩個星球之間可以透過一對或者多對傳送裝置來抵達。

目前民間的機構已經設置了 m 對的傳輸裝置，兔子王打算再設置更多的傳輸裝置來增加國家的GDP。其中必須滿足以下的條件：

1.兩個固定的星球之間最多只能有一對傳輸裝置(國王專屬的不算)
2.基於安全考量，愚民們從星球 1 通行到星球 2 的最短時間不可以低於 250 分鐘。
你可以假設在所有的測資當中，所有星球皆連通，並且星球 1 與星球 2 的最短路徑大於 250 分鐘。

兔子王想知道，他最多還可以多設置幾對傳輸裝置。

Input:Output:

第一行有兩個正整數 n,m (n ≤ 40000, m ≤ 1000000)，代表星球個數以及目前民間設置的傳輸裝置對數。
接下來有 m 行，每行兩個數字 Ai,Bi ，代表有一對裝置直接連接 Ai 號星球以及 Bi 號星球。
你可以假設透過民營的傳輸裝置，星球 1 與 2 也是連通的，並且最短所需要花費的時間大於 250 分鐘。

輸出一個數字，代表還可以再設置幾對裝置。

Sample Input:Sample Output:

10 10
1 3
3 5
5 7
7 9
2 9
1 4
4 6
6 8
8 10
2 10

HINT:

實線為現有的傳輸裝置，虛線為新增的。
在滿足限制的情況，最多可以增加10條。

Source:

POI 17 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-ocen	1000ms	65536kb
1-1	2000ms	65536kb	8
1-2	2000ms	65536kb
1-3	2000ms	65536kb
1-4	2000ms	65536kb
1-5	2000ms	65536kb
2-ocen	1000ms	65536kb
2-1	2000ms	65536kb	8
2-2	2000ms	65536kb
2-3	2000ms	65536kb
3-ocen	2000ms	65536kb
3-1	2000ms	65536kb	8
3-2	1000ms	65536kb
4-ocen	5000ms	65536kb
4-1	2000ms	65536kb	8
4-2	2000ms	65536kb
4-3	2000ms	65536kb
5-1	2000ms	65536kb	8
5-2	2000ms	65536kb
5-3	2000ms	65536kb
6-1	2000ms	65536kb	8
6-2	2000ms	65536kb
7-1	3000ms	65536kb	8
7-2	3000ms	65536kb
8-1	4800ms	65536kb	8
8-2	4800ms	65536kb
9-1	4800ms	65536kb	9
9-2	4800ms	65536kb
10-1	6000ms	65536kb	9
10-2	6000ms	65536kb
11-1	9000ms	65536kb	9
11-2	3000ms	65536kb
12-1	9000ms	65536kb	9
12-2	9000ms	65536kb