Help Shams

Time Limit: 2.5 sec

 

The Problem

Shams, a software engineer from Hamelin just got placed in a software company in Gamilins. As, he have to relocate from Hamelin to Gamilin, he decided to buy a house. Yeah price of houses have decreased in Shams Country. He decided to buy a house in a locality which has burger points at each corner. As the streets are only one way there is a heavy traffic jam and it take time to Shams to reach burger point. The Mayor has declared that some streets connecting these burger points to two way roads. Some conversion cost is associated with each street. It will cost lot of money to convert all streets to two way streets so Mayor wanted these conversion in such a way that total cost of conversion is minimized keeping in mind that all burger points are connected with two way roads. Shams after coming to know about this idea decided to buy a house in a two way street. But not all streets will be two way. So, he asked you to tell him if he should buy house in a particular street or not. As there can be more than one conversion plan, help Shams to decide if he should buy house in that street or not. You will be given m queries by Shams. Your task is to tell for how many queries the answer will be yes. Return answer in the form of a/b where a is the no. of queries for which answer is yes and b is total number of queries. (gcd(a,b) should be 1).

There will be n burger points and k streets joining them.

 

The Input

First line of input contain 1 integer t(1<=t<=15) denoting the number of test cases.

Next line of input will contain 2 positive integers n and k where n( 1<=n<=1000)  is the number of burger points and k is the number of streets connecting them.

Burger points are numbered 1 to n.

Next k line contain 3 positive integers x,y,c (<1000000) each denoting street between x and y and c is the cost associated with that street.
Next line contains 1 integer m denoting number of queries.
Next m line contains 2 integers e,r.

 

The Output

Output answer in the form as specified in question. For more clarity see sample test case.

 

Sample Input

1

7

10

1 2 5

1 4 3

1 5 12

1 6 5

4 5 1

5 6 2

5 3 1

3 6 16

4 7 1

2 4 1

5

1 6

2 4

3 5

3 6

1 2

 

Sample Output

2/5

 

 

Explanation

For the queries 2 and 3 there can be a two way road. Hence, total number of yes are 2 and total queries are 5 and hence the answer is 2/5. 

 

Inter University Programming Contest - 2016 [BGC Trust University Bangladesh]

Problem Setter: Parag Paul