MikukuOvO @ 2019-10-15 17:50:18
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define il inline
struct EDGE
{
int to,nxt;
};
struct temp
{
int st,ed;
};
const int N=1e5+5;
const int M=1e6+5;
int n,m,p,ans,sigma,top,id,num,cnt;
int dfn[N],low[N],stk[N],sum[N],f[N],g[N];
int head[N],idx[N],odx[N],col[N];
EDGE e[M];
temp w[M];
bool ins[N],vis[N];
il bool cmp(temp x,temp y)
{
if(col[x.st]==col[y.st]) return col[x.ed]<col[y.ed];
return col[x.st]<col[y.st];
}
il void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
w[cnt].st=x,w[cnt].ed=y;
}
il void Tarjan(int x)
{
dfn[x]=low[x]=++id;
stk[++top]=x,ins[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
if(!dfn[e[i].to]) Tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
else if(ins[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
}
if(low[x]==dfn[x])
{
num++;
while(stk[top+1]!=x)
{
sum[num]++;
col[stk[top]]=num;
ins[stk[top]]=0;
top--;
}
}
}
il void dfs(int x)
{
vis[x]=1;
if(!odx[x])
{
f[x]=sum[x],g[x]=1;
ans=max(ans,f[x]);
return;
}
for(int i=head[x];i;i=e[i].nxt)
{
if(!vis[e[i].to]) dfs(e[i].to);
if(f[x]<f[e[i].to]+sum[x]) f[x]=f[e[i].to]+sum[x],g[x]=g[e[i].to],ans=max(ans,f[x]);
else if(f[x]==f[e[i].to]+sum[x]) g[x]+=g[e[i].to],g[x]%=p;
}
}
int main()
{
freopen("semi.in","r",stdin);
freopen("semi.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
for(int i=1,x,y;i<=m;++i) scanf("%d%d",&x,&y),add(x,y);
for(int i=1;i<=n;++i) if(!dfn[i]) Tarjan(i);
cnt=0;
memset(e,0,sizeof(e)),memset(head,0,sizeof(head));
sort(w+1,w+m+1,cmp);
for(int i=1;i<=m;++i)
{
if(col[w[i].st]!=col[w[i].ed]&&(col[w[i].st]!=col[w[i-1].st]||col[w[i].ed]!=col[w[i-1].ed]))
{
add(col[w[i].st],col[w[i].ed]);
idx[col[w[i].ed]]++,odx[col[w[i].st]]++;
}
}
for(int i=1;i<=num;++i) if(!idx[i]&&!vis[i]) dfs(i);
for(int i=1;i<=num;++i) if(f[i]==ans) sigma+=g[i],sigma%=p;
printf("%d\n%d",ans,sigma);
return 0;
}
```