Problem D
Húsatengingar

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, $0 \leq n, m \leq 10^5$ þar sem $n \neq 0$ er fjöldi bygginga og $m$ er fjölda innanhúsatenginga sem eru þegar til staðar. Byggingarnar eru númeraðar frá $1$ og upp í $n$. Næst koma $m$ línur, hver með tveimur tölum $1 \leq a, b \leq n$ sem merkir að þegar sé til staðar innanhúsaleið milli byggingar númer $a$ og byggingar númer $b$. Engin leið fer frá byggingu í sjálfa sig og ekki eru gefnar margar leiðir milli sömu tveggja bygginganna. Næsta línan í inntakinu inniheldur eina heiltölu $1 \leq q \leq 10^5$, fjölda fyrirspurna. Næst fylgja $q$ línur, hver með einni fyrirspurn. Lína með fyrirspurn byrjar á einni heiltölu $1 \leq t \leq 3$ sem segir til um hvers konar fyrirspurn þetta er.

Fyrirspurnir eru af eftirfarandi gerðum:

• 1 a b: Bæta á við innanhúsarleið milli byggingar númer $a$ og byggingar númer $b$, með $a != b$. 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 $a$ og byggingar númer $b$, með $a != b$. 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 $a$ og $b$ eru heiltölur og brotið er fullstytt. Ef líkurnar eru $0$ 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 $3$ eins og lýst er að ofan.

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