P7729 交通运输（Wormhole Transportaion）

**本题数据点较多，请勿恶意提交。如发现恶意提交的，可能面临封号的处罚。** 天体风暴过后，永恒大陆的交通急需重建。

永恒大陆上有 $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$ 取模的结果。

**【样例 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$ | $12$ | $2000$ | 由所有 $(u_i,v_i)$ 为无向边构成的图为仙人掌森林 | $3$ | | $4$ | $25$ | $2000$ | 由所有 $(u_i,v_i)$ 为无向边构成的图为杏仁 | $8$ | | $5$ | $27$ | $300$ | $m\leq 1000$ | $8$ | | $6$ | $14$ | $2000$ | 无 | $3$ | 仙人掌森林：每条边在至多一个简单环中的无向图。 杏仁：恰好存在两个度数大于 $2$ 的结点，其他结点度数都等于 $2$，且所有环都经过两个度数大于 $2$ 的结点的连通无向图。 当你对于某个子任务的所有测试点，**第一问都回答正确，但第二问没有都回答正确**，你将获得这个子任务的部分分。