题目描述

有向图的顶点 $u$ 和 $v$ 被称为强连通的，如果存在一条从 $u$ 到 $v$ 的路径，并且存在一条从 $v$ 到 $u$ 的路径。注意，如果 $u$ 和 $v$ 强连通，且 $v$ 和 $w$ 强连通，那么 $u$ 和 $w$ 也强连通。因此，图中的顶点被划分为若干个强连通分量。属于同一个强连通分量的顶点彼此强连通（包括其本身），并且与任何不属于该分量的顶点都不强连通。

在一次图论课上，Alice 在黑板上画了一个包含 $n$ 个顶点的有向图，并且高亮了图中的强连通分量。课间，Bob 决定恶作剧，他想删除图中一些边的方向，并且希望 Alice 能够根据剩下的边和课间的强连通分量划分，唯一地恢复这些被删除方向的边。

帮助 Bob 确定最大可以删除的边数，以及可以删除这些边的方案数。

更正式地说，找到一个边的子集 $A$，使得如果我们删除集合 $A$ 中边的方向，则根据剩下的边的方向以及强连通分量的划分信息，可以唯一地恢复集合 $A$ 中边的方向，从而保持图的强连通分量不变。并且，求出这个子集 $A$ 的最大大小，以及这个子集的方案数。

由于这样的方案数可能非常大，输出该数对 $10^9 + 7$ 取模的结果。

如果正确计算了最大子集的大小，但方案数计算错误，则将获得部分分数。

输入格式

第一行包含三个整数 $n$、$m$ 和 $g$（$2 \le n \le 2000$，$1 \le m \le 2000$，$0 \le g \le 7$）—— 图中的顶点数、边数以及测试组编号。

接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）—— 第 $i$ 条边的起点和终点。

保证对于任意的 $1 \le i, j \le n$，$(u_i, v_i) \neq (u_j, v_j)$ 且 $(u_i, v_i) \neq (v_j, u_j)$，即任意两点之间最多有一条边，无论方向如何。

输出格式

输出两行。

第一行输出一个整数——可以删除的最大边子集的大小。

第二行输出一个整数——该子集的方案数对 $10^9 + 7$ 取模的结果。如果你不想输出方案数，则在第二行输出任意一个从 $-1$ 到 $10^9 + 6$ 之间的数字。若第二行没有输出正确的数字，则无论子集大小是否正确，都会被判定为“错误答案”，并且该测试得分为零。

输入输出样例 #1

输入 #1

5 6 0
1 2
1 5
2 3
3 4
3 5
4 2

输出 #1

3
3

说明/提示

样例解释

在这个样例中，图的强连通分量如下图所示：

可以删除虚线边的方向。实际上，边 $(1, 5)$ 不能反向，因为如果反向，顶点 $1$、$2$、$3$、$5$ 将属于同一个强连通分量。同样，边 $(3, 4)$ 和 $(4, 2)$ 也不能反向，因为这样 $2$、$3$、$4$ 将不属于同一个强连通分量。

现在，考虑一个错误的子集选择方式：

这里，虚线加粗边的方向不能删除。例如，如果我们将边 $(1, 2)$ 和 $(1, 5)$ 的方向反向，得到的图依然会有相同的强连通分量划分。

可以证明，有 $4$ 条边的方向不能删除，因此正确答案是 $3$。

评分

本题的测试点共包含七个分组。分组的分数规则如下：

如果正确计算了最大边子集的大小和该子集的方案数，并且在该分组的所有测试点中都正确，用户将获得该分组的满分。

如果正确计算了最大子集的大小，但方案数计算错误，则将为该分组获得部分分数。此时，依赖该分组的分组也将进行测试，并且可能获得满分。

组别	部分分数	满分分数	限制条件：$n$	限制条件：$m$	依赖组别	说明
0			--			样例测试点。
1	7	11	$n \le 14$	$m \le 14$	0
2	5	9	$n \le 20$	$m \le 20$	0, 1
3	8	12	--		--	满足 $u_i < v_i$，对于所有 $1 \le i \le n - 1$，存在一条边 $(i, i + 1)$。
4		13			3	满足 $u_i < v_i$。
5	12	20			--	对于所有 $1 \leqslant i \leqslant n - 1$，存在一条边 $(i, i + 1)$，且存在一条边 $(n, 1)$。
6	13	21			5	图是一个强连通分量。
7	8	14			0 -- 6