22745_RouteRedundancy

A city if made up exclusively of one-way streets. Each street in the city has a capacity, the maximum number of cars it can carry per hour. Any route (path) also has a capacity，which is the minimum of the capacities of the streets along that route.

The redundancy ratio from point A to point B is the ratio of the maximum number of cars that can get form A to B in an hour using all routes simultaneously, to the maximum number of cars that can get from A to B in an hour using just one route. The minimum redundancy ratio is the number of cars that can get from A to B in an hour using all possible routes simultaneously, divided by the capacity of the single route with the largest capacity.

The first line of input contains a single integer P , ( 1 ≤ P ≤ 1000 ),which is the number of data sets that follow. Each data set consists of several lines and represents a directed graph with positive integer weights.

The first line of each data set contains five space separated integers. The first integer, D is the data set number. The second integer, N ( 2 ≤ N ≤ 1000 ), is the number of edges in the graph. The fourth integer, A ( 0 ≤ A < N ), is the index of point A. The fifth integer, B, ( 0 ≤ B < N, A ≠ B ), is the index of point B.

The remaining E lines describe each edge. Each line contains three space separated integers. The first integer, U ( 0 ≤ U < N ), is the index if node U, The second integer, V ( 0 ≤ V < N , V  ≠ U ), is the index of node V. The third integer, W ( 1 ≤ W < 1000 ), is the capacity (weight) of the path from U  to V.

For each date set there is one line of output. It contains the data set number (N) followed by a single space, followed by a floating-point value which is the minimum redundancy ratio to 3 digits after the decimal point.

1
1 7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

1 1.667