For many years, Absurdistan was famous for its camel caravans. However, the new Grand Vizier decided to make a radical step towards civilization – he will actually build some roads.
On the other hand, too many roads would unnecessarily confuse the local inhabitants. (That, and camels don’t really like walking on roads.) Therefore the road network will, for now, have to be minimal, just enough to connect all the villages.
Preliminary investigations were made. For some pairs of villages we know a lower and an upper estimate of the cost of building a direct road between these two villages.
The Grand Vizier has made you personally responsible for preparing the budget. You know that after you prepare the budget, the exact cost for each potential road will be computed, and the best set of roads will be selected.
Problem specification
There are N villages in Absurdistan. There are M pairs of villages such that we can build a direct road that connects them. For each such road i, we know the minimal cost li and the maximal cost ui.
The builders will first find the exact cost for each road, and then select the cheapest set of roads that connects all the villages.
Assuming that for each road its true cost is a real-valued random variable with uniform distribution over the interval [li,ui], compute the expected cost of the road network.
Notes
All roads are bidirectional.
The roads are built in such a way that they don’t intersect anywhere, using bridges if necessary. Thus in order to connect N villages you have to build at least N - 1 roads.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of several lines. The first line of a test case contains two integers N and M, giving the number of villages and the number of possible roads, respectively. The villages are numbered from 0 to N - 1. M lines follow, each of them describes one possible road. Each description consists of four integers: the villages connected xi and yi, and the minimum and maximum cost li and ui.
Villages are numbered starting from zero. All costs are non-negative. The input graphs are somewhat special, it may be worth your while to examine the input data before attempting to solve the task.
Output specification
For each test case, the output shall contain one line with the expected cost of the cheapest road network. This value is always rational, and you are to output it as the simplest possible fraction.
Print the fraction as A∕B, with no spaces. Even if B = 1, print the denominator.
If for some test case it is not possible to build any road network that connects all villages, output -1 instead.
Examples
| input
4
3 2 0 1 0 9 1 2 10 11 4 2 0 1 10 11 1 2 10 12 3 3 0 1 0 1 1 2 2 2 0 2 3 3 3 3 0 1 0 1 1 2 0 1 0 2 0 1 |
| output
15/1
-1 5/2 3/4 In the first test case, we have to build both roads. Their expected costs are 9∕2 and 21∕2, which gives a total of 30∕2 = 15∕1. In the second test case, we can not connect village 4 to the other villages. In the third test case, the two cheapest roads are always 1 - 2 and 2 - 3, with total expected cost 1∕2 + 2 = 5∕2. The fourth test case illustrates that the builders first find out the exact road costs, and only then pick the best set. In this case, we generate three random numbers from [0,1], and the result is the expected sum of the smaller two. |