Smart City

Imagine a smart city where (1) only self-driving cars are used, (2) all streets are bidirectional, cars pass each of them in one time unit, and, consequently, the road network of the city can properly be modelled by a connected, unweighted, undirected graph.

Given such a graph (n: number of nodes; m: number of edges; nodes are denoted by 1, 2, …, n), for each pair of nodes A and B, we imagine having one unit of “flow” along the edges from A to B. More precisely, the flow between A and B divides itself evenly along all the possible shortest paths from A to B: so if there are k shortest paths from A to B, then 1/k units of flow pass along each one.

We define the traffic of an edge to be the total amount of flow it carries, counting flow between all pairs of nodes using this edge.

We are interested in the most vital edge of the graph, the one that carries the highest volume of traffic along shortest paths.

Input Specification

The first line of the input contains the number of test cases. For each test case, the first line contains two integers, the values of n and m (separated by a single space). The next m lines contain the endpoints of the edges (separated by a single space).

Input Limits and Constraints

• 1 < n < 1000;
• 0 < m < 20 000.

Output Specification

For each test case, print one line with three integers separated by a single space: the highest traffic value and the endpoints of the corresponding edge. If there are multiple edges with maximal traffic value, then print the first one in lexicographical order.

Sample Input

1. 2
2. 2 1
3. 1 2
4. 14 17
5. 1 2
6. 1 3
7. 2 3
8. 3 7
9. 4 5
10. 4 6
11. 5 6
12. 6 7
13. 7 8
14. 8 9
15. 8 12
16. 9 10
17. 9 11
18. 10 11
19. 12 13
20. 12 14
21. 13 14

download as text file

Output for Sample Input

1. 1 1 2
2. 49 7 8

download as text file