题目描述

一套单向信号网络由 $n$ 座中继站和 $m$ 条单向传输通道组成。若存在一条从中继站 $i$ 指向中继站 $j$ 的通道，则信号可以在一个时间单位内从 $i$ 直接传到 $j$。

用一个 $n\times n$ 的 01 矩阵 $A$ 描述网络，其中 $A_{i,j}=1$ 当且仅当存在一条从 $i$ 到 $j$ 的直接传输通道。

矩阵之间采用布尔乘法。若 $C=A\times B$，则

$$C_{i,j}=\bigvee_{k=1}^{n}\left(A_{i,k}\land B_{k,j}\right),$$

其中 $\lor$ 表示逻辑或，$\land$ 表示逻辑与。于是，$A^x_{i,j}=1$ 当且仅当信号能够恰好经过 $x$ 条通道从中继站 $i$ 到达中继站 $j$。

随着传播步数不断增加，整个网络在“恰好传播若干步后能够到达哪些中继站”这一状态上最终会进入周期。

请找出最小的正整数 $k,d$，使得对于所有 $i\ge k$，均有

$$A^i=A^{i+d}.$$

其中 $k$ 表示进入稳定周期前的最短等待时间，$d$ 表示最短周期长度。答案需要对 $10^9+7$ 取模。

在部分测试中，只需要求出 $d$。

输入格式

第一行三个整数 $n,m,t$，其中 $n,m$ 分别表示中继站数量和单向传输通道数量。若 $t=1$，则需要同时求出最小的 $k$；否则只需要求出 $d$。

接下来 $m$ 行，每行两个整数 $u,v$，表示存在一条从中继站 $u$ 指向中继站 $v$ 的单向传输通道。

输出格式

一行，如果 $t=1$ 则输出两个整数 $k,d$，否则只输出一个整数 $d$。

样例

样例 1 输入

5 5 1
1 2
2 3
3 4
4 5
5 3

样例 1 输出

2 3

样例 1 解释

数据范围与提示

对于所有测试点，$1\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq u,v\leq n$，$0\leq t\leq 1$。