Optimal Wormhole Construction

On the Eternal Continent there are \(n\) bases numbered \(1,2,\ldots,n\). There are \(m\) transportation tasks; the \(i\)th task is to transport cargo from base \(u_i\) to base \(v_i\). In the post‐disaster era, the road network is poor. Therefore you decide to build wormholes. You can build a wormhole between any two different bases \(x\) and \(y\). Once built, cargo can travel from one end to the other in \(1\) unit of time, and the wormhole is bidirectional.

However, because building wormholes is expensive, you insist on constructing exactly \(m-1\) wormholes (and you cannot build two wormholes connecting the same pair of bases). With this constraint you are free to choose which wormholes to build. Once built, the \(i\)th transportation task will take time equal to the distance between \(u_i\) and \(v_i\) in the constructed network (where each wormhole counts as \(1\) unit on the unique simple path between any two bases that are connected).

Your goal is twofold:

1. Minimize the total time spent on the \(m\) tasks.
2. Count, modulo \(10^9+7\), the number of wormhole construction schemes (i.e. choices of \(m-1\) distinct wormhole pairs) that achieve that minimum total time.

Note: It is allowed that the wormholes do not connect all bases overall. However, for each transportation task, the two bases \(u_i\) and \(v_i\) must lie in the same connected component so that the task can be completed.

Hint (and a key observation): To minimize the transport time, you want as many tasks as possible to have a direct wormhole between their endpoints. Since you have exactly \(m-1\) wormholes but \(m\) tasks, at least one task will have to use an indirect connection (with a path length at least 2). In fact, if all bases involved in tasks are connected (assume for simplicity that the tasks involve all \(n\) bases so that the \(m-1\) wormholes form a spanning tree) then it can be proved that a star tree minimizes the sum of distances. In a star with center \(r\), any task that has \(r\) as one endpoint takes time \(1\), and any task between two leaves takes time \(2\). Therefore if we let \(d_r\) be the frequency (number of tasks) in which base \(r\) appears (i.e. tasks directly incident to \(r\)), the total time is

[ T = 2m - d_r. ]

Thus the optimal strategy is to choose as center a base \(r\) having maximum \(d_r\). When several choices are possible the number of schemes is the number of such optimal centers. (In the general case where tasks do not cover all bases there will be a similar decomposition by connected components but you may assume that all bases are involved in tasks.)

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n \le 10^5,\; 1 \le m \le 10^5)\). Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) \((1 \le u_i, v_i \le n,\; u_i \neq v_i)\) representing a transportation task from base \(u_i\) to base \(v_i\>.

You may assume that it is possible to build exactly \(m-1\) wormholes so that for every transportation task, the two bases are connected.

outputFormat

Output two integers separated by a space: the first is the minimum possible total time for all \(m\) tasks, and the second is the number of wormhole construction schemes achieving that minimum total time, modulo \(10^9+7\).

sample

3 2
1 2
2 3

2 1