强连通再度出击

有向图中的两个顶点 $u$ 和 $v$ 被称为强连通的，当且仅当图中存在从 $u$ 到 $v$ 的路径，同时也存在从 $v$ 到 $u$ 的路径。

注意：若 $u$ 与 $v$ 强连通，且 $v$ 与 $w$ 强连通，则 $u$ 与 $w$ 也强连通。因此，图中的顶点会被划分为若干集合——强连通分量。属于同一个强连通分量的顶点两两之间强连通（包括自身），与分量外的任意顶点都不强连通。

在一节图论课上，Alice 在黑板上画了一张有 $n$ 个顶点的有向图，并标出了它的强连通分量。课间时，Bob 想捉弄 Alice，他擦掉了图中部分边的方向。 Bob 希望：在擦掉部分边的方向之后，Alice 能够根据剩余边的方向以及原图的强连通分量划分，唯一地还原出所有被擦掉方向的边。

请你帮助 Bob 求出：他最多能擦掉多少条边的方向，以及有多少种选取最大边集的方案。

更形式化地说： 求出满足以下条件的边子集 $A$ 的最大大小，以及这样的最大子集 $A$ 的数量（对 $10^9+7$ 取模）：

• 将子集 $A$ 中所有边的方向抹去；
• 仅依靠原图的强连通分量信息与不在 $A$ 中的边的方向，就可以唯一地还原出 $A$ 中每条边的方向，使得还原后的图强连通分量与原图完全一致。

---

输入格式

第一行包含三个整数 $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$ 条有向边为 $u_i \to v_i$。

保证：任意两点之间至多存在一条边（无论方向），即对任意 $i,j$ 都满足 $(u_i, v_i) \neq (u_j, v_j)$ 且 $(u_i, v_i) \neq (v_j, u_j)$。

---

输出格式

第一行输出一个整数：最多可以抹去方向的边的数量。 第二行输出一个整数：满足最大数量的选取方案数，对 $10^9+7$ 取模。

---

样例输入输出

标准输入

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

标准输出

3
3

---

样例说明

标记得出的强连通分量为： $\{1\}, \{2,3,4\}, \{5\}$

可以抹去方向的边为虚线边。事实上：

• 边 $(1,5)$ 不能反向，否则顶点 $1,2,3,5$ 会处于同一个强连通分量；
• 边 $(3,4)$ 与 $(4,2)$ 也不能反向，否则顶点 $2,3,4$ 不再属于同一个强连通分量。

考虑一种不合法的选取方式： 若同时抹去 $(1,2)$ 和 $(1,5)$ 的方向，则存在两种不同的定向方式，都能得到相同的强连通分量，因此不合法。

可以证明：恰好有 $4$ 条边不能抹去方向，因此最多可抹去 $3$ 条。

---

评分规则

测试点分为 $7$ 组，只有通过某一组及所有前置要求的组别才能获得对应分数。

额外约束

组别	分数	$n$ 限制	$m$ 限制	前置组别	额外说明
$0$		—			样例
$1$	$11$	$n \le 14$	$m \le 14$	$0$
$2$	$9$	$n \le 20$	$m \le 20$	$0,1$
$3$	$12$	—		—	所有边满足 $u_i < v_i$；对 $1\le i\le n-1$ 存在边 $i\to i+1$
$4$	$13$			$3$	所有边满足 $u_i < v_i$
$5$	$20$			—	对 $1\le i\le n-1$ 存在边 $i\to i+1$，且存在边 $n\to 1$
$6$	$21$			$5$	整张图是一个强连通分量
$7$	$14$			$0\sim 6$