Minimal Fault Tolerant Set

A telecommunications company has a large network of (n) servers numbered from (1) to (n) that are connected by (m) bidirectional communication channels. It is guaranteed that these servers are all reachable from one another.\n\nWe call a set of servers (A) a fault tolerant set if and only if, for any single channel failure (i.e. the removal of any edge), the following condition holds: for every server (X \notin A), there exists at least one server (Y \in A) such that data can be transmitted from (Y) to (X) using the remaining channels (i.e. in the graph (G-e)).\n\nThe company wishes to store backup data on multiple servers, but to minimize cost, they want the backup servers to form a fault tolerant set of minimum size. In addition, they would like to know in how many different ways such a set can be chosen. Since the number of ways may be large, output it modulo (10^9+7).\n\nA key observation is that if we contract the network into its 2-edge-connected components (i.e. after removing all bridges) and form a tree, then every bridge in the original network corresponds to an edge connecting two such components. In any valid fault tolerant set, each leaf component in this tree must contribute at least one server. Therefore, if the network is not 2-edge-connected (i.e. there is at least one bridge), the minimal fault tolerant set consists of exactly all servers chosen (one from each leaf 2-edge-connected component) and the number of ways is the product of the sizes of these leaf components. Otherwise, when the network is 2-edge-connected, a single server is sufficient and there are (n) ways to choose it.

inputFormat

The first line contains two integers (n) and (m) ((1 \le n \le 10^5), (0 \le m \le 10^5)), representing the number of servers and the number of communication channels, respectively. The following (m) lines each contain two integers (u) and (v) ((1 \le u,v \le n)), denoting a bidirectional channel connecting servers (u) and (v). It is guaranteed that the network is connected.

outputFormat

Output two integers separated by a space: the minimum number of servers in a fault tolerant set, and the number of different ways to choose such a set modulo (10^9+7).

sample

2 1
1 2

2 1