Hide

Problem W
Húsatengingar

The students of the University of Iceland are still trying to convince the higher-ups to build more indoors paths between buildings so they don’t have to wade through the snow or walk through torrential rains to get between classes. The higher-ups have been looking into this possibility, but for some reason the Icelandic state probabilist was put in charge. He started wondering what the probability of adding some indoor path between two buildings who didn’t already have one helping with the problem would be. The path is chosen uniformly randomly among all pairs of buildings that do not have a direct indoors path between them already. The path is considered to help with the problem if the total number of pairs of buildings that can be traveled between using some sequence of indoors paths increases by adding this new path. Could you solve this problem so he’ll get around to his actual duties?

Input

The first line of the input contains two integers $0 \leq n, m \leq 10^5$ where $n \neq 0$ is the number of buildings and $m$ is the number of indoors paths already present. The buildings are numbered from $1$ to $n$. Next there are $m$ lines, each with two integers $1 \leq a, b \leq n$ giving that there is an indoors path present between building number $a$ and building number $b$. No path will go from a building to itself and there will be at most one path between any given pair of buildings. The next line in the input contains one integer $1 \leq q \leq 10^5$, the number of queries. Next follow $q$ lines, each with one query. A line with a query starts with an integer $1 \leq t \leq 3$, denoting the type of query. The types are as follows:

  • 1 a b: An indoors path should be added between building number $a$ and building number $b$, $a \neq b$. If there is already such a path the query should be ignored.

  • 2 a b: The indoors path between building number $a$ and building number $b$ should be removed, $a \neq b$. If there is no such path the query should be ignored.

  • 3: Print the probability described above. The probability should be printed in the form a/b where $a, b$ are integers and the fraction is fully reduced. If the probability is zero or no path can be added, print 0/1.

Output

Print one line for each query of type $3$ as described above.

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

Please log in to submit a solution to this problem

Log in