P2272
RT，参考的是第二篇题解

#include<bits/stdc++.h>
#define N 100000+20
using namespace std;
int n,m,p,ind,cnt;
int dfn[N],low[N],sd[N],sum[N],f[N][3];
bool instack[N],flag[N];
stack<int>st;
vector<int>g[N],g1[N];
void tarjan(int u)
{
	instack[u]=1;
	dfn[u]=low[u]=++ind;
	st.push(u);
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		sd[u]=++cnt;
		while(1)
		{
			int v=st.top();
			sd[v]=cnt;
			sum[cnt]++;
			instack[v]=0;
			st.pop();
			if(u==v)break;
		}
	}
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
	{
		f[i][1]=sum[i];
		f[i][2]=1;
		for(int j=0;j<g[i].size();j++)
		{
			int u=sd[i],v=sd[g[i][j]];
			if(u!=v)
			{
				g1[u].push_back(v);
			}
		}
	}
	for(int i=cnt;i>=1;i--)
	{
		for(int j=0;j<g1[i].size();j++)
		{
			int u=i,v=g1[i][j];
			if(flag[v]==u)continue;
			flag[v]=u;
			if(f[v][1]<f[u][1]+sum[v])
			{
				f[v][1]=f[u][1]+sum[v];
				f[v][2]=f[u][2];
			}
			else if(f[v][1]==f[u][1]+sum[v])
			{
				f[v][2]+=f[u][2];
				f[v][2]%=p;
			}
		}
	}
	int ans1=-1,ans2=0;
	for(int i=1;i<=cnt;i++)
	{
		if(f[i][1]>ans1)
		{
			ans1=f[i][1];
			ans2=f[i][2];
		}
		else if(f[i][1]==ans1)ans2=(ans2+f[i][2])%p;
	}
	cout<<ans1<<endl<<ans2;
	return 0;
}