## 引入

$$A^1 = \left[\begin{matrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{matrix}\right]$$

$$A^2 = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$$

$$A^3 = \left[ \begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right]$$

$$A^4 = \left[ \begin{array}{ccccc} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{array} \right]$$

$$A^5 = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$$

## 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
const int maxl=2e2+1;
const int md=1e9+7;
typedef long long ll;

int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}

ll gcd(ll x,ll y){
return y?gcd(y,x%y):x;
}

ll lcm(ll x,ll y){
return y?x*y/gcd(x,y):x;
}

vector<int>to[maxn];
int n,m,ty;

int dfn[maxn],low[maxn],id[maxn];
int vis[maxn],sta[maxn];
ll nd[maxn],ans_d=1;
int val[maxn];
int top,cnt,tot;

void Tarjan(int u){
dfn[u]=low[u]=++cnt;
sta[++top]=u;vis[u]=1;
for (auto v:to[u]){
if (!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u]){
++tot;
int k=-1;
while(k!=u){
k=sta[top--];
id[k]=tot;
vis[k]=0;
}
}
}

void dfs(int u,int d){
vis[u]=1;val[u]=d;
for (auto v:to[u]){
if (id[v]!=id[u]) continue;
if (!vis[v]) dfs(v,d+1);
else if (val[v]!=d+1){
nd[id[u]]=gcd(nd[id[u]],(ll)abs(d+1-val[v]));
}
}
}

struct matrix{
bitset<maxl>a[maxl];
inline void set(){
for (register int i=1;i<=n;++i) a[i][i]=1;
}
inline matrix operator * (const matrix x) const{
matrix res;
for (register int i=1;i<=n;++i)
for (register int k=1;k<=n;++k) if (a[i][k])
res.a[i]|=x.a[k];
return res;
}
inline bool operator == (const matrix x) const{
for (register int i=1;i<=n;++i)
if (a[i]!=x.a[i]) return 0;
return 1;
}
}grp,sone;

matrix qpow(matrix a,ll b){
matrix res=sone;
while(b){
if (b&1) res=res*a;
b>>=1;a=a*a;
}
return res;
}

ll qpow(ll a,ll b){
ll res=1;
while(b){
if (b&1) res=res*a%md;
a=a*a%md;b>>=1;
}
return res;
}

ll solve(){
int p=1;
matrix lst=grp;
while(1){
if (qpow(grp,p+ans_d)==lst) break;
lst=qpow(lst,2);p<<=1;
}
ll l=max(p/2,1),r=p,res=1;
while(l<=r){
ll mid=(l+r)>>1;
if (qpow(grp,mid+ans_d)==qpow(grp,mid))
res=mid,r=mid-1;
else l=mid+1;
}
return res;
}

int prm[maxn];

int main(){
sone.set();
for (register int i=1;i<=m;++i){
to[a].push_back(b);
grp.a[a][b]=1;
}
for (register int i=1;i<=n;++i)
if (!dfn[i]) Tarjan(i);
memset(vis,0,sizeof(vis));
for (register int i=1;i<=n;++i)
if (!vis[i]) dfs(i,0);
for (register int i=1;i<=tot;++i){
for (register int k=2;k<=nd[i];++k){
if (nd[i]%k) continue;
int tmp=0;
while(!(nd[i]%k)) tmp++,nd[i]/=k;
prm[k]=max(prm[k],tmp);
}
}
for (register int i=1;i<=n;++i)
ans_d*=qpow(i,prm[i]);
printf("%lld ",solve());
printf("%lld\n",ans_d);
}