TopCoder

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

8.7% (17/195)

Description

經過一番角逐,新任國王烏龜已經選出來了--正確地說,只有一隻烏龜合乎上文所述條件。
所以理所當然地,他成為了新任的國王。

「『你』,過來看一下,這是烏龜王國的地圖。」RK招呼你過去看一張地圖。

這張地圖上有 N座都會區,表示烏龜國的幾個重要都會區。
然後圖上標有 M條交通路徑,每條交通路徑連接兩座都會區,
表示這兩座都會區可以直接往來。(可能是步行、公車、水上摩托車、游泳或獨木舟之類的。)

RK拍了拍地圖,道:「新任的國王一定住在國內某座都會區內,他也會選擇另一座都會區蓋
皇宮,然後就會有很盛大的遊行儀式,國王會從他所居住的都會區遷移到皇宮所在都會區……」
(根據傳統,皇宮絕對不能跟原本祝所在同一座大都會--這樣就沒辦法遊行了。)

『你』插了話:「可是我們不是已經把上一任國王轉學了嗎?那麼為什麼還要調查這些路徑?」

RK不理會你,繼續說道:「到時候我們會派出 K隻埋伏部隊,埋伏在其中 K條交通道路上,
當國王烏龜一出現就可以綁架他到我們基地來,切記要生的不要殺了他。」

「可是根本無法知道他會用哪些交通路徑啊?」你困惑著。

RK輕蔑地望著你,眼神彷彿在說這種問題像小學課本習題一樣簡單似的。

「可以發現的是,假設知道了起點跟終點,有些道路是一定得經過的。
有一定的機率,這種一定要走的道路恰好 K條,就可以每條都埋伏一隻部隊了!
切記,多了或少了都不行,因為少了就埋伏不了這麼多部隊、多了可能會被其他人乘虛而入……」
語至此,RK突然摸了摸自己的殼,似乎有著什麼不好的回憶。

『你』實在搞不懂他葫蘆裡賣著什麼藥,「可是我們連起點和終點都不知道?」
RK還是正眼不看你一下「可以算一下機率啊,分母很明顯是 N×(N-1),而分子是……」

他把這個問題丟給了你,也就是有少點對之間的必經道路剛好 K條?
(起點終點交換視為相異。)

Input Format

對於40% 測試資料,N ≤ 1,000; M ≤ 5,000;
對於100% 測試資料,N ≤ 200,000; M ≤ 500,000;
對於50% 測試資料,K=1;
對於80% 測試資料,1 ≤ K ≤ 5;
對於100% 測試資料,1 ≤ K ≤ 300;
對於30% 測試資料,N ≤ 1,000; M ≤ 5,000; K=1;

第一行有三個數字,N, M, K。依序表示大都會數目、交通道路數目以及 K。
接下來有M行,每行兩個數字 I, J,表示大都會 I跟大都會 J 有直接的交通道路。
對於兩個大都會 可能有不只一條直接的交通道路連結

Output Format

輸出僅含一行一個數字 A, 表示機率是A / [N×(N-1)]。

Sample Input

5 5 2
1 2
2 3
1 3
3 4
4 5

Sample Output

6

Hints

1 -> 5
2 -> 5
3 -> 5
5 -> 1
5 -> 2
5 -> 3

Problem Source

原TIOJ1709 / 建國中學99年校內培訓contest #7 prob 5
problem setter:ATP、worm

Subtasks

No. Testdata Range Score
1 0~1 20
2 2 10
3 3 10
4 4 10
5 5 10
6 6~8 20
7 0~12 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1 7
1 1500 65536 262144 1 7
2 1500 65536 262144 2 7
3 1500 65536 262144 3 7
4 1500 65536 262144 4 7
5 1500 65536 262144 5 7
6 1500 65536 262144 6 7
7 1500 65536 262144 6 7
8 1500 65536 262144 6 7
9 1500 65536 262144 7
10 1500 65536 262144 7
11 1500 65536 262144 7
12 1500 65536 262144 7