第一行：两个整数，表示缩点后的节点数和边数.

接下来，每行两个整数，表示两点有一条边.

#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;
		}
	}
	
	int sumf=0;
	for(int i=1;i<=stknum;i++)sumf+=g[i].size();
	cout<<stknum<<" "<<sumf<<endl;
	for(int i=1;i<=stknum;i++){
		for(int j:g[i])cout<<i<<" "<<j<<endl;
	}
	
	
//	cout<<ans<<endl<<sum%s<<endl;//注意取模
}