Lucifero @ 2021-05-10 22:22:29
#include <bits/stdc++.h>
using namespace std;
class Edge
{
public:
int u,v,next;
}e[1000001],s[1000001];
stack<int> r;
queue<int> ind;
bool ins[100001];
int elast[100001],slast[100001],pin[100001],n,link1,link2;
int cnt[100001],way[100001],mark[100001],ans1,ans2,X;
int dfn[100001],low[100001],order;
int belong[100001],size[100001],scc;
void e_add(int u,int v)
{
e[++link1]=(Edge){u,v,elast[u]};
elast[u]=link1;
}
void s_add(int u,int v)
{
s[++link2]=(Edge){u,v,slast[u]};
slast[u]=link2;
}
void tarjan_scc(int u)
{
int v,i;
dfn[u]=low[u]=++order;
r.push(u),ins[u]=true;
for(i=elast[u];i!=0;i=e[i].next);
{
v=e[i].v;
if (dfn[v]==0)
{
tarjan_scc(v);
low[u]=min(low[u],low[v]);
}
else if (ins[v])
low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u])
{
scc++,v=0;
do
{
v=r.top();
r.pop(),ins[v]=false;
belong[v]=scc;
size[scc]++;
}while(!r.empty() && u!=v);
}
}
int main()
{
//最大半连通子图
int m,a,b,u,v,uu,vv,i;
scanf("%d%d%d",&n,&m,&X);
while(m--)
{
scanf("%d%d",&a,&b);
e_add(a,b);
}
for(i=1;i<=n;i++)
if (dfn[i]==0) tarjan_scc(i);
for(u=1;u<=n;u++)
{
cnt[u]=size[u],way[u]=1;
for(i=elast[u];i!=0;i=e[i].next);
{
v=e[i].v;
uu=belong[u],vv=belong[v];
if (uu!=vv) s_add(uu,vv);
}
}
for(u=scc;u>=1;u--)
for(i=slast[u];i!=0;i=s[i].next)
{
v=s[i].v;
if (mark[v]==u) continue;
mark[v]=u;
if (cnt[v]<cnt[u]+size[v])
{
cnt[v]=cnt[u]+size[v];
way[v]=way[u];
}
else if (cnt[v]==cnt[u]+size[v])
way[v]=(way[v]+way[u])%X;
}
for(i=1;i<=scc;i++)
if (ans1<cnt[i])
ans1=cnt[i],ans2=way[i];
else if (ans1==cnt[i])
ans2=(ans2+way[i])%X;
printf("%d\n%d",ans1,ans2%X);
}