P11026 [COTS 2020] 抗疫 Autoritet

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

有 $N$ 个国家，$M$ 条双向航线连接不同的国家。需要注意的是，两个国家之间可能有多条航线连接。 疫情当下，欲举全球之力共同抗疫，需要将世界联结。定义世界是**联结的**，当且仅当任意两个国家都通过航线直接或间接相连。 我们记 $V=\{1,2,\cdots,N\}$。在一次操作中： - 任意选择 $u\in V$； - 令集合 $S$ 为国家 $u$ 通过**恰好一条**航线能够到达的国家的集合；令集合 $T=V\backslash \{u\}\backslash S$。 - $\forall v\in S$，将连接 $u,v$ 的航线删除；$\forall w\in T$，添加连接 $u,w$ 的航线。 可以证明，添加足够多的航线后，一定能够使世界联结。 欲通过最少的操作次数使世界联结。 求出： - 最少的操作次数 $k$； - 在最小化操作次数的前提下，不同的操作序列数量。只需要求出对 $(10^9+7)$ 取模后的结果。 定义两个操作序列是不同的，当且仅当存在 $i\in [1,k]$，使得在这两个操作序列中第 $i$ 次选择的国家 $u$ 不同。

第一行，两个正整数 $N,M$。 接下来 $M$ 行，第 $i$ 行两个正整数 $a_i,b_i$，描述一条航线 $(a_i,b_i)$。

输出两行，每行一个整数，表示对应的答案。 其中第二问的答案需要对 $(10^9+7)$ 取模。

#### 样例解释 - 样例 $1$ 解释：存在不需要执行任何操作的情况。 - 样例 $2$ 解释：所有的操作序列有 $[1,4],[4,1],[2,3],[3,2]$。 #### 评分方式 如果回答对了第一问，可以获得 $15\%$ 的分数。 如果不打算回答第二问，也要任意输出一个 $\in [0,10^9+7)$ 的整数，否则不保证得分符合预期。 #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le N,M\le 5\times 10^5$； - $a_i\neq b_i$。 | 子任务编号 | $N,M\le $ | 得分 | | :--: | :--: | :--: | | $ 1 $ | $18$ | $ 5 $ | | $ 2 $ | $300$ |$ 9 $ | | $ 3 $ | $3\, 000$ | $ 16 $ | | $ 4 $ | $5\times 10^5$ | $ 70 $ |