Background

Translated from Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D2T1。$\texttt{2s,0.5G}$。

Problem Description

There are $N$ countries and $M$ undirected air routes connecting different countries. Note that there may be multiple routes between the same pair of countries.

During the epidemic, to unite the world to fight against it, we need to connect the world. The world is defined to be connected if and only if any two countries are connected directly or indirectly through air routes.

Let $V=\{1,2,\cdots,N\}$. In one operation:

• Choose any $u\in V$。
• Let set $S$ be the set of countries that country $u$ can reach via exactly one air route; let set $T=V\backslash \{u\}\backslash S$。
• For all $v\in S$, delete the air routes connecting $u$ and $v$; for all $w\in T$, add an air route connecting $u$ and $w$。

It can be proven that after adding enough air routes, the world can always be made connected.

You want to make the world connected using the minimum number of operations.

Output:

• The minimum number of operations $k$。
• Subject to minimizing the number of operations, the number of different operation sequences. You only need the result modulo $(10^9+7)$。

Two operation sequences are considered different if and only if there exists some $i\in [1,k]$ such that the country $u$ chosen in the $i$-th operation is different in the two sequences.

Input Format

The first line contains two positive integers $N,M$。

The next $M$ lines each contain two positive integers $a_i,b_i$, describing an air route $(a_i,b_i)$。

Output Format

Output two lines, each containing one integer, representing the corresponding answers.

The answer to the second question should be taken modulo $(10^9+7)$。

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

0
1

4 2
1 4
2 3

2
4

8 9
1 4
2 3
6 7
8 5
2 4
7 8
5 6
6 8
4 3

1
5

Hint

Sample Explanation

• Sample $1$: there is a case where no operations are needed。
• Sample $2$: all operation sequences are $[1,4],[4,1],[2,3],[3,2]$。

Scoring

If you answer the first question correctly, you can get $15\%$ of the score.

If you do not plan to answer the second question, you still need to output any integer in $[0,10^9+7)$, otherwise the score is not guaranteed to be as expected.

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1\le N,M\le 5\times 10^5$；
• $a_i\neq b_i$。

Translated by ChatGPT 5