TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

22.9% (8/35)

Tags

Description

你知道GATE嗎? 知道為什麼GATE世界裡為何大叔可以開後宮嗎?
不知道沒關係,因為伊丹其實也不太清楚,在路途上就收了N個後宮。另外還有三個正宮候補,我們姑且將她們稱為藍毛、金毛、黑毛。

伊丹和他的正宮候補們

除了藍毛、金毛和黑毛之外的這N個後宮,他們為了維繫感情,想要有互相連繫溝通的方法,可是你知道異世界的電信網路還沒有這麼完善,所以他們會透過魔法或是奇怪的工具來建立連線,也就是溝通的管道。
但是如果每個人都要和其他人的建立連線,總共需要N*(N-1)/2次動作,這實在是太麻煩了。
於是她們約好了,就是用最少的連線讓這N個人可以直接或是間接的連線,非常聰明的你一定知道只要(N-1)次連線就可以把全部的後宮連繫在一起。

看似無害的藍毛

但是有一天,平時悶聲不吭看似無害心機卻很重的藍毛心情不是很好。她認為伊丹實在開太多後宮了,所以她想要讓這N個後宮物理上的消失(或是化學上的、也可能是魔法上的?)。心胸寬大的金毛和961歲的黑毛覺得這實在是太不人道了,她們決定要偷偷幫助其中某些後宮活下來。

心情不是很好的藍毛

我們知道藍毛是很聰明的心機女,在展開屠殺的晚上,她會先找到一個後宮,切斷他和其他人的連線,讓她沒辦法呼救,然後再慢慢的...把她...,嗯,你知道的。但是後宮很多藍毛沒有那麼多時間,所以他會先挑連線數量只有一條的後宮,這樣很輕鬆的就可以切斷他的連線,當這個後宮被解決之後,其他的後宮可能就會減少一個可以求救的對象,藍毛就有機會可以再對其他的後宮出手。她會重複屠殺直到所有人都死亡,因為只有(N-1)條連線,如果黑毛和金毛不做任何事,那藍毛將會屠殺所有的後宮。
黑毛和金毛決定阻止藍毛的邪惡計劃,她們打算在後宮間多增加一些連線,這樣當其中一條被切斷了,那個後宮還可以馬上用另外一條連線向其他人求救,藍毛當然不希望事蹟敗露,所以她發現一個後宮有兩條以上的連線時,他就會選擇放過這個後宮。
雖然黑毛和金毛心胸寬大,但是黑毛和金毛礙於身份行動不方便(其實他們也覺得後宮太多了?),她們 只會幫某一對後宮建立連線 ,聰明的你一定知道這樣總共會出現N條聯繫,也就不會讓所有人都被藍毛給殺掉。

心機很重的藍毛

因為不知道要救誰,金毛和黑毛決定先一人挑選一個和自己感情最好的後宮,金毛和黑毛將會找一種方法讓這兩人能活下來。讓這兩人能活下來的方法不只一種,而且每種選擇會導致最後能活下來的人數也不一樣。
金毛和黑毛其實並不是很care他們的好朋友之外的其他的後宮是生是死,他們只要能救到他們兩個各自的好朋友就好,所以她們只會從可以拯救那兩人的方法中隨機選一種方法建立連線。

比起其他後宮,黑毛對衣服比較有興趣

於是問題就來了,在所有方法機率都相等的情況下,不同的方法會活下來的人數也不同,那最後到底會活下來多少人呢?雖然不能確定會活下來多少人,但是我們可以算出活下來人數的期望值是多少。
我們擁有這N個後宮原本的聯繫關係,但是我們並不明白金毛和黑毛最後會選擇哪兩個後宮而行動;根據不能說的可靠情報來源,黑毛和金毛可能會選M種組合,請你計算這M種組合,最後能夠活下來的人數期望值分別是多少。

Input Format

第一行有兩個正整數N和M( 2 <= N,M <= 100000 ),定義見題敘。
第二行到第N行每行兩個正整數a和b( 1 <= a,b <= N ),代表a和b之間有一條連線。當然,這些連線都是雙向的。
接下來M個詢問,每行兩個正整數p和q( 1<= p,q <= N , p!=q ),代表p和q是黑毛和金毛可能想要救的兩個人。

Output Format

對於每個詢問,請輸出最後能夠活下來的人數期望值是多少。請輸出分數格式 a/b,並約成最簡分數。

Sample Input 1

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

Sample Output 1

4/1
3/1
3/1

Hints

對於範例測資,一開始的連線長的像這樣「3-2-4-1」
如果不做任何事,藍毛可以選擇先除掉3,2就只剩下和4之間的一條連線,就可以再解決2...,依序解決所有人。
第1種組合,黑毛和金毛決定救3和1,於是他們只能在3和1之間建立連線,會拯救4個人,期望值是4。
第2種,黑毛和金毛決定救2和3,於是他可以在[3,2][3,4][3,1]之間建立連線,分別會整救2、3、4個人,期望值是3。特別解釋[3,2]這條連線,因為3和2之間會有兩條連線,藍毛沒辦法一次切斷兩條連線,所以她會放過這兩個人。

Problem Source

Gate:洪駿輝

Subtasks

No. Testdata Range Score
1 0~2 20
2 3~12 40
3 13~22 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 2
4 1000 65536 262144 2
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 2
11 1000 65536 262144 2
12 1000 65536 262144 2
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 3
16 1000 65536 262144 3
17 1000 65536 262144 3
18 1000 65536 262144 3
19 1000 65536 262144 3
20 1000 65536 262144 3
21 1000 65536 262144 3
22 1000 65536 262144 3