P11026 [COTS 2020] Anti-epidemic Autoritet

Translated from [Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2020/) D2T1。$\texttt{2s,0.5G}$。

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.

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 two lines, each containing one integer, representing the corresponding answers. The answer to the second question should be taken modulo $(10^9+7)$。

#### 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$。 | Subtask ID | $N,M\le $ | Score | | :--: | :--: | :--: | | $ 1 $ | $18$ | $ 5 $ | | $ 2 $ | $300$ |$ 9 $ | | $ 3 $ | $3\, 000$ | $ 16 $ | | $ 4 $ | $5\times 10^5$ | $ 70 $ | Translated by ChatGPT 5