Description

There are $n$ bases on Eternal Continent, numbered $1, 2, \ldots, n$.

Now there are $m$ transportation tasks. The $i$-th task is: transport goods from base $u_i$ to base $v_i$.

However, transportation after the disaster is not well developed, so you decide to use wormholes. You can build a wormhole between any two different bases $x, y$. Transporting goods from one end of the wormhole to the other end only takes $1$ unit of time.

Also, transportation is bidirectional. That is, if you build a wormhole connecting bases $a$ and $b$, then goods can be transported from base $a$ to base $b$, and also from base $b$ to base $a$.

But building wormholes is expensive. You decide to build exactly $\boldsymbol{m - 1}$ wormholes, and no two wormholes may connect the exact same pair of bases.

You want to know, among all construction plans, what is the minimum possible total time spent for the $m$ transportation tasks. In addition, under the condition that this total time is minimized, how many different wormhole construction plans are there.

Since the answer to the second question may be very large, you only need to output it modulo ${10}^9 + 7$.

Input Format

The first line contains three integers $n, m, t$, where $t$ is the subtask ID. For the samples, $t=0$.

The next $m$ lines each contain two integers $u_i, v_i$.

Output Format

The first line contains one integer, the minimum total time spent for the $m$ transportation tasks.

The second line contains one integer, the number of wormhole construction plans modulo ${10}^9 + 7$.

3 3 0
1 2
2 3
3 1

4
3

5 6 0
1 2
2 3
1 4
4 3
1 5
5 3

8
30

Hint

[Sample 1 Explanation]

There are three construction plans.

One plan is to build wormholes between cities $1, 2$ and between cities $2, 3$. Then the time for the first two tasks is $1$, and the time for the last task is $2$.

The other two plans are: build wormholes between cities $1, 2$ and $1, 3$, or build wormholes between cities $1, 3$ and $2, 3$.

[Constraints]

For all data, $2 \le n \le 2000$, $2 \le n \cdot m \le 2 \times {10}^7$, $1 \le u_i, v_i \le n$, and $u_i \ne v_i$.

It is guaranteed that all unordered pairs $(u_i, v_i)$ are pairwise distinct, and that there exists at least one valid wormhole construction plan.

Cactus forest: an undirected graph in which each edge belongs to at most one simple cycle.

Almond: a connected undirected graph in which there are exactly two vertices with degree greater than $2$, all other vertices have degree exactly $2$, and all cycles pass through the two vertices with degree greater than $2$.

If for all test points of a subtask, your answer to the first question is all correct, but your answer to the second question is not all correct, you will receive the partial score for this subtask.

Translated by ChatGPT 5