遮云壑 @ 2021-06-27 22:44:39
#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
inline void read(int& x)
{
x=0;
int y=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x=x*y;
}
int n,m,mod;
struct edge{
int to,next;
}e[maxn];
int cnt=0,head[10010];
inline void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int dfn[10010],low[10010],st[10010],top,ins[10010],tim;
int totscc,scc[10010],belong[10010];
void tarjan(int x)
{
dfn[x]=low[x]=++tim;
st[++top]=x;ins[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(dfn[y]==0)
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
totscc++;
int k;
do{
k=st[top];top--;
ins[k]=0;
belong[k]=totscc;
scc[totscc]++;
}while(k!=x);
}
}
int h[10010],cnt_;
edge ed[maxn];
inline void add_(int u,int v)
{
ed[++cnt_].to=v;
ed[cnt_].next=h[u];
h[u]=cnt_;
}
struct node{
int u,v;
bool operator <(const node &x)const
{
if(u==x.u)return v<x.v;
else return u<x.u;
}
}a[maxn];
int in[10010],cntt;
inline void rebuild()
{
for(int x=1;x<=n;x++)
{
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(belong[x]!=belong[y])
{
a[++cntt].u=belong[x];
a[cntt].v=belong[y];
}
}
}
sort(a+1,a+1+cntt);
for(int i=1;i<=cntt;i++)
{
if((a[i].u==a[i-1].u)&&(a[i].v==a[i-1].v))continue;
add_(a[i].u,a[i].v);
in[a[i].v]++;
}
}
int f[10010],Dp[10010];
queue<int> q;
inline void dp()
{
for(int i=1;i<=totscc;i++)
{
if(in[i]==0)
{
q.push(i);
f[i]=scc[i];
Dp[i]=1;
}
}
while(q.size())
{
int x=q.front();
q.pop();
for(int i=h[x];i;i=ed[i].next)
{
int y=ed[i].to;
if(f[y]==f[x]+scc[y])
{
Dp[y]+=Dp[x];
Dp[x]%=mod;
}
if(f[y]<f[x]+scc[y])
{
f[y]=f[x]+scc[y];
Dp[y]=Dp[x];
}
in[y]--;
if(in[y]==0)q.push(y);
}
}
}
int main(){
read(n),read(m),read(mod);
int u,v;
for(int i=1;i<=m;i++)
{
read(u),read(v);
add(u,v);
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)tarjan(i);
}
rebuild();
dp();
int ans1=0,ans2=0;
for(int i=1;i<=totscc;i++)
{
if(f[i]>ans1)
{
ans1=f[i];
ans2=Dp[i];
}
else if(f[i]==ans1)
{
ans2+=Dp[i];
ans2%=mod;
}
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}