Rescue Exit Placement

A coal mine can be modeled as an undirected graph where vertices represent coal extraction points and edges represent the tunnels connecting them. For safety reasons, the mine owner wants to install rescue exits at some of the coal points such that no matter which coal point collapses, the workers at every other coal point have a road that leads to at least one rescue exit.

Formally, let the mine be represented by an undirected graph with n vertices and m edges. We wish to choose a set S of vertices (the locations of the rescue exits) with the minimum possible size such that for any vertex u (which might collapse), in every connected component of the graph G \( \setminus \{u\} \) there is at least one vertex from S. In other words, after the removal of any vertex, every remaining connected component must contain a rescue exit.

It can be shown that the answer depends on the structure of the graph. In particular, if the graph is originally connected:

• If n = 1 (i.e. the graph has only one vertex), then the only possibility is to place a rescue exit at that vertex.
• If the graph is 2-connected (i.e. it has no articulation points), then the minimum number of exits required is 2 and the number of ways is \( \binom{n}{2} \) (i.e. choose any 2 vertices).
• If the graph has one or more articulation points, one can show (using the block tree of biconnected components) that the answer is determined by the number of leaf blocks in the block tree. For each such leaf block (which always contains exactly one articulation vertex), if its size is \( k \) then it contributes \( k-1 \) choices. Hence if there are \( L \) leaf blocks, the minimum number of exits is L and the number of ways is the product of \( (\text{size}_i - 1) \) over all leaf blocks \( i \).

When the graph is not connected, each connected component must be handled independently. For a component with only one vertex, the answer is 1 way. Otherwise, compute the answer for that component as above and then the overall minimum number of rescue exits is the sum of the minimum numbers from each component and the overall number of ways is the product of the ways for each component.

The mathematical formulas used are in LaTeX format. For example, the number of ways for a 2-connected component is given by \( \binom{n}{2} = \frac{n(n-1)}{2} \).

inputFormat

The first line contains two integers n and m \( (1 \leq n \leq 10^5,\, 0 \leq m \leq 10^5) \) representing the number of coal points (vertices) and tunnels (edges) respectively. The following m lines each contain two integers u and v (1-indexed) indicating that there is an undirected edge connecting vertices u and v (a tunnel between them).

You may assume that the graph may be disconnected. In each connected component:

• If the component has a single vertex, the answer for that component is 1 1.
• If the component has no articulation point then the answer is 2 \( \;\; \frac{n(n-1)}{2} \) for that component.
• If the component has at least one articulation point then let L be the number of biconnected components (leaf blocks in the block tree) that contain exactly one articulation point and for each such block of size \( k \) contribute \( k-1 \) ways. The minimum exits for that component is L and the number of ways is the product of all these contributions.

outputFormat

Output two space‐separated integers: the minimum number of exits needed and the total number of different ways to place them. When the graph is disconnected, compute the answer separately for each connected component and combine them by summing the minimum numbers and multiplying the ways.

sample

1 0

1 1