Route Redundancy#3555
A city consists exclusively of one-way streets, each with a certain capacity. The capacity of a route is defined as the minimum of the capacities of the streets along that route.
The redundancy ratio from point to point is the ratio of the maximum number of cars that can travel from point to point in one hour using all possible routes simultaneously, to the maximum number of cars that can travel using just a single route in one hour. The minimum redundancy ratio equals the capacity of the single route with the largest capacity.
The first line of input contains an integer (1 \le P \le 1000), the number of data sets.
Each data set consists of several lines and describes a directed graph with positive integer weights.
The first line of each data set contains five space-separated integers: , , , , and . Here, is the data set number; (2 \le N \le 1000) is the number of nodes in the graph; (E \ge 1) is the number of edges; (0 \le A < N) is the index of point ; (0 \le B < N,\, A \ne B) is the index of point .
The following lines each describe an edge with three space-separated integers: , , and . Here, (0 \le U < N) is the start node, (0 \le V < N,\, V \ne U) is the end node, and (1 \le W \le 1000) is the capacity (weight) of the edge from to .
For each data set, output a single line containing the data set number (), followed by a space, then the minimum redundancy ratio, rounded to decimal places.
Example 1