Problem W
Húsatengingar
Languages
en
is
Enn berjast nemendur Háskóla Íslands fyrir því að geta komist milli bygginga án þess að vaða í gegnum snjó eða ganga í rigningunni. Því var ákveðið að rannsaka þann kost að bæta við nýjum neðanjarðargöngum milli tveggja bygginga. Einhverra hluta vegna endaði það sem svo að líkindafræðingurinn á svæðinu fékk að stjórna skipulagi þessa verks. Því fór hann að velta fyrir sér hverjar líkurnar væru á að ný göng valin af handahófi myndi gera ástandið eitthvað betra. Göngin eru valin með jöfnum líkum yfir öll pör húsa sem eru ekki með göng á milli sín nú þegar. Göng eru sögð gera ástandið betra ef fjöldi para húsa sem ferðast má milli innanhúss (eftir mögulega fleiri en einni göng) fjölgar. Getur þú leyst þetta verkefni svo hann komi sér einhvern tímann að verki?
Inntak
Fyrsta línan í inntakinu inniheldur tvær heiltölur,
Fyrirspurnir eru af eftirfarandi gerðum:
-
1 a b: Bæta á við innanhúsarleið milli byggingar númer
og byggingar númer , með . Ef þegar er til staðar innanhúsaleið sem liggur milli bygginganna á ekki að gera neitt. -
2 a b: Vegna skemmda eða annarra uppákoma á að fjarlægja leiðina milli bygginar númer
og byggingar númer , með . Ef ekki er innanhúsaleið milli bygginganna á ekki að gera neitt. -
3: Prenta skal líkurnar sem lýstar eru að ofan. Prenta á líkurnar á forminu a/b þar sem
og eru heiltölur og brotið er fullstytt. Ef líkurnar eru eða ekki er hægt að bæta við neinum legg á að prenta 0/1.
Úttak
Prenta á út eina línu fyrir hverja fyrirspurn af gerðinni
Sample Input 1 | Sample Output 1 |
---|---|
5 1 1 2 16 2 1 2 3 1 1 2 3 1 2 3 3 1 2 3 1 3 4 3 1 1 4 3 1 4 5 3 2 1 2 2 1 4 3 |
1/1 1/1 7/8 4/7 2/3 0/1 4/7 |