题目背景

本题数据点较多，请勿恶意提交。如发现恶意提交的，可能面临封号的处罚。

天体风暴过后，永恒大陆的交通急需重建。

题目描述

永恒大陆上有 $n$ 个基地，基地编号为 $1, 2, \ldots , n$。

现在有 $m$ 条运输任务，第 $i$ 条形如：将货物从基地 $u_i$ 运输到基地 $v_i$。

然而灾后交通并不发达，因此你决定使用虫洞：可以在任意两个不同基地 $x,y$ 之间建立一个虫洞：货物从虫洞的一端传输到虫洞的另一端只需要花费 $1$ 单位的时间。

而且，运输的方向是双向的，也就是说，假设建立了一个连接了基地 $a, b$ 的虫洞，那么货物既可以从基地 $a$ 运输到基地 $b$，也可以从基地 $b$ 运输到基地 $a$。

但建立虫洞的代价是昂贵的，你决定只建立恰好 $\boldsymbol{m - 1}$ 个虫洞，且不能有两个虫洞连接的两个基地完全相同。

你想要知道，在所有的建造方案中， $m$ 条运输任务所花费的时间之和最小能是多少，此外，在花费的时间之和最小的情况下，有多少种建造虫洞的方案。

由于第二个问题的答案可能很大，你只需要输出方案数对 ${10}^9 + 7$ 取模的结果。

输入格式

第一行：三个整数 $n,m,t$，其中 $t$ 为子任务编号，对于样例来说 $t=0$。

接下来 $m$ 行：每行两个整数 $u_i,v_i$。

输出格式

第一行，一个整数，表示 $m$ 条运输任务所花费的时间之和的最小值。

第二行，一个整数，表示建造虫洞的方案数对 ${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

提示

【样例 1 解释】

有三种建造方案。

其中一种是在城市 $1, 2$ 之间建立虫洞，在城市 $2, 3$ 之间建立虫洞，这样，前两条任务的时间都为 $1$，最后一条的时间为 $2$。

另外两种方案是：在城市 $1, 2$ 和 $1, 3$ 之间建立虫洞，或在城市 $1, 3$ 和 $2, 3$ 之间建立虫洞。

---

【数据范围】

对于所有数据，$2 \le n \le 2000$，$2 \le n \cdot m \le 2 \times {10}^7$，$1 \le u_i, v_i \le n$，$u_i\ne v_i$。

保证所有无序对 $(u_i, v_i)$ 两两不同，且至少存在一种合法的建造虫洞的方案。

子任务编号	分值	$n \le$	特殊限制	部分分
$1$	$10$	$6$	无	$0$
$2$	$12$	$2000$	$m=n$，且 $u_i=i,\ v_i=i\bmod n+1$	$3$
$3$			由所有 $(u_i,v_i)$ 为无向边构成的图为仙人掌森林
$4$	$25$		由所有 $(u_i,v_i)$ 为无向边构成的图为杏仁	$8$
$5$	$27$	$300$	$m\leq 1000$
$6$	$14$	$2000$	无	$3$

仙人掌森林：每条边在至多一个简单环中的无向图。

杏仁：恰好存在两个度数大于 $2$ 的结点，其他结点度数都等于 $2$，且所有环都经过两个度数大于 $2$ 的结点的连通无向图。

当你对于某个子任务的所有测试点，第一问都回答正确，但第二问没有都回答正确，你将获得这个子任务的部分分。