思路

可以发现，一个SCC一定是半连通子图，所以我们可以先缩点，形成DAG.

然后，我们会发现，缩完点的图中，最大半连通子图一定是一条链。因为最大半连通子图中两点之间一定有路径，如果有分叉，则分叉的两端没有到达对方的路径，不满足最大半连通子图的性质.

需要注意的是，整个图需要判重边，不然可能会重复计算.

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=500001;
vector<int>edge[MAXN];
int instk[MAXN],dfn[MAXN],low[MAXN],belong[MAXN],tot,stknum,ans,n,m;
vector<int>scc[MAXN];
stack<int>stk;
//edge: 原来节点的边
//instk,dfn,low,belong,tot,stknum(scc数量): tarjan模板
//ans: 最大半连通子图大小
//n,m: 点数和边数

vector<int>g[MAXN];
int f[MAXN];
//g: 缩点以后的图
//f[i]: 缩点以后，以i节点开始 可以组成的 节点最多 的链的大小

set<pair<int,int>>st;
//st: 用于判重边

int mem[MAXN],s;
//mem: dfs记忆化用的

void tarjan(int x){
	dfn[x]=low[x]=++tot,instk[x]=1;
	stk.push(x);
	
	for(int i:edge[x]){
		if(!dfn[i]){
			tarjan(i);
			low[x]=min(low[x],low[i]);
		}
		else if(instk[i]){
			low[x]=min(low[x],dfn[i]);
		}
		
	}
	
	if(dfn[x]==low[x]){
		int y;
		stknum++;
		
		do{
			y=stk.top();
			stk.pop();
			scc[stknum].emplace_back(y);
			instk[y]=0;
			belong[y]=stknum;
			
		}while(y!=x);
		
		/*---模板分界线---*/
		
		for(int a:scc[stknum]){
			for(int z:edge[a]){
				if(belong[a]!=belong[z])g[stknum].emplace_back(belong[z]);//建新图
			}
		}
		
		for(int i:g[stknum]){
			f[stknum]=max(f[stknum],f[i]);//找出 链大小最大 的儿子
		}
		
		f[stknum]+=scc[stknum].size();//加上自己的大小
		ans=max(ans,f[stknum]);
	}
}
int dfs(int u){
	if(mem[u])return mem[u];
	int sum=0;
	
	for(int v:g[u]){
		if(f[u]==f[v]+(int)scc[u].size())sum+=dfs(v);//只有大小符合需求的点才可以加上
		sum%=s;//注意取模
	}
	
	if(!sum)sum=1;//叶子节点只有1种情况
	
	mem[u]=sum%s;
	return sum%s;
}
signed main(){
	cin>>n>>m>>s;
	if(n>m+1){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		edge[u].emplace_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	
	/*---模板分界线---*/
	
	for(int i=1;i<=stknum;i++){//判重边：记录所有边
		for(int j:g[i])st.insert({i,j});
		g[i].clear();
	}
	
	for(auto i=st.begin();i!=st.end();i++){//判重边：把边放回去
		g[i->first].emplace_back(i->second);
	}
	
	int sum=0;
	
	for(int i=1;i<=stknum;i++){
		if(f[i]==ans){//从 最大链的开始 的节点开始计算
			sum+=dfs(i);
			sum%=s;
		}
	}
	
	cout<<ans<<endl<<sum%s<<endl;//注意取模
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int dfn[maxn],low[maxn],belong[maxn],sccsize[maxn];
pair<int,long long> dp[maxn];// first:最大节点数, second:方案数
int in[maxn];
vector<int> g[maxn],scc[maxn],new_g[maxn];// 新增缩点后的图
stack<int> stk;
bool instk[maxn],vis[maxn];
int n,m,mod,t=0,totscc=0;
void tarjan(int u){
	dfn[u]=low[u]=++t;
	stk.push(u);
	instk[u]=true;
	for(int v:g[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(instk[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}if(low[u]==dfn[u]){
		totscc++;
		int v;
		do	v=stk.top(),
			stk.pop(),
			instk[v]=false,
			belong[v]=totscc,
			scc[totscc].push_back(v),
			sccsize[totscc]++;
		while(v!=u);
	}
}void build_new_graph(){
	set<pair<int,int>>edges;// 使用set去除重边
	for(int u=1;u<=n;u++)
		for(int v:g[u])
			if(belong[u]!=belong[v])// 避免重复添加相同边
				if(edges.find({belong[u],belong[v]})==edges.end()){
					edges.insert({belong[u],belong[v]});
					new_g[belong[u]].push_back(belong[v]);
					in[belong[v]]++; // 更新入度
				}
}void solve(){// 拓扑排序+DP
	queue<int>q;
	for(int i=1;i<=totscc;i++){
		dp[i]={sccsize[i],1}; // 初始值：只包含当前SCC
		if(in[i]==0)q.push(i);
	}while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int v:new_g[u]){
			in[v]--;
			if(in[v]==0)q.push(v);
			// 更新DP值
			if(dp[u].first+sccsize[v]>dp[v].first)
				dp[v].first=dp[u].first+sccsize[v],
				dp[v].second=dp[u].second%mod;
			else if (dp[u].first+sccsize[v]==dp[v].first)
				dp[v].second=(dp[v].second+dp[u].second)%mod;
		}
	}
}int main() {
	scanf("%d%d%d",&n,&m,&mod);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
	}
	// 1. Tarjan求强连通分量
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	// 2. 缩点建新图（处理重边）
	build_new_graph();
	// 3. 拓扑排序 + DP
	solve();
	// 4. 统计答案（找全局最大值）
	int max_nodes=0;
	long long count=0;
	for(int i=1;i<=totscc;i++)
		if(dp[i].first>max_nodes)
			max_nodes=dp[i].first,
			count=dp[i].second%mod;
		else if(dp[i].first==max_nodes)
			count=(count+dp[i].second)%mod;
	printf("%d\n%lld\n",max_nodes,count%mod);
	return 0;
}