题目背景

译自 Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) 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)$ 取模。

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

提示

样例解释

• 样例 $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$