TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

中世紀,是一個忙碌的世紀,城市與城市之間的溝通往往都是由各個驛站派出快馬,在指定時間內將訊息從某個城市送達另一個城市。在拜特阿瑟所居住的國家裡,也有這一類的快馬通信系統。不過有趣的是,每匹快馬只認得兩個城市,因此牠只能在這兩個城市之間往來。這種快馬還有一種神奇的特性,那就是牠每趟傳訊的時間恰好都是一個小時


身為一個國家安全部門的秘密偵查員,拜特阿瑟建立了與總部連線的裝置,每一次的訊息傳遞因為使用的是皇家快馬,恰好需要兩百五十分鐘(超過四個小時)的時間就可以將訊息從拜特阿瑟所在的城市2傳回首都城市1。


中世紀,是一個資訊爆炸的世紀。許多城市都很希望訓練出與其他城市之間能夠往來的快馬,因此全部向中央申請增加原本沒有的快馬傳信路線。但是拜特阿瑟發現,在城市2當中疑似有恐怖組織的活動,若他們能夠利用快馬通信系統在四個小時之內與首都城市1溝通的話,那麼皇家快馬便沒有辦法趕在發生緊急事故的時候早一步通知首都的安全部門。


請你幫個忙,在不違背上述安全顧慮的情況下,找出許可最多申請的文件數。

Input Format

輸入可能包含多筆測試資料。每一筆測試資料的第一列包含兩個正整數N以及M (2<=N<=40000; 0<=M<=1000000),分別代表城市的數量和快馬路線的數量。城市的編號從1到N。接下來的M列每一列有兩個正整數A < B代表城市A和城市B之間有快馬傳訊。每一對城市(A, B)至多只會出現一次。而且以目前的通信系統來看,的確有一種間接傳訊的方式使訊息可以在城市1和城市2之間傳遞,但是所耗費的時間絕對超過皇家快馬所需要的時間。

Output Format

對於每一筆測試資料請輸出至多能夠增加的快馬路線的數量。

Sample Input 1

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

Sample Output 1

10

Hints

Problem Source

Migrated from old NTUJ.

POI17th, stage II. prob4

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 200