#include <bits/stdc++.h>

using namespace std;
int ppt;
struct edng{
	int to,nxt;
}e[1000002];
int cnt,head[100002],color[100002];
int bbb=0,ans=0;
bool vis[100005];
int dfn[100006],low[100005],gshu[100005];
bool kun[100005];
stack <int> s;
inline int read(){
	int x=0,f=1,ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
void dfs(int x){
	bbb++;
	vis[x]=true;
	dfn[x]=low[x]=bbb;
	s.push(x);
	for(int i=head[x];i;i=e[i].nxt){
		if(dfn[e[i].to]==false){
			dfs(e[i].to);
			low[x]=min(low[x],low[e[i].to]);
		}else if(vis[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
	}
	if(low[x]==dfn[x]){
		ans++;
		int tmp=-1;
		do{
			tmp=s.top();
			s.pop();
			color[tmp]=ans;
			vis[tmp]=0;
			gshu[ans]++;
		}while(tmp!=x);
	}
}
int hhh[100005];
int Max=INT_MIN;
int ll=0;
int AK[100005];
int aa[100005];
inline int dfs(int yanse,int sum){
	kun[yanse]=true;
	
	int o=0,kkk=0;
	int gg=0;
	for(int i=head[yanse];i;i=e[i].nxt){
		int rjl=e[i].to;
		if(kun[rjl]==false){
			kkk=max(kkk,dfs(rjl,sum+gshu[yanse]));
		}
		//2 3 1 4 5 6 7
		if(kun[rjl]==true){
			if(o<AK[rjl]){
				gg=aa[rjl];
				o=AK[rjl];
			}else if(o==AK[rjl]){
				gg+=aa[rjl];
			}
		}
	}
	hhh[sum+o+gshu[yanse]]+=max(gg,1);
	hhh[sum+o+gshu[yanse]]=hhh[sum+o+gshu[yanse]]%ppt;
	Max=max(sum+o+gshu[yanse],Max);
	AK[yanse]=max(o,kkk)+gshu[yanse];
	aa[yanse]=max(gg,1); 
	return o+gshu[yanse];
}
struct node{
	int xx,yy;
}hi[1000005];
int cmp(node bbc,node ccb){
	if(bbc.xx!=ccb.xx){
		return bbc.xx<ccb.xx;
	}else{
		return bbc.yy<ccb.yy;
	}
}
int cmpp(node bbc,node ccb){
	if(color[bbc.xx]!=color[ccb.xx]){
		return color[bbc.xx]<color[ccb.xx];
	}else{
		return color[bbc.yy]<color[ccb.yy];
	}
}
int main(){
	int n,m;
	cin>>n>>m>>ppt;
	for(int i=1;i<=m;i++){
		int x,y;
		hi[i].xx=read();
		hi[i].yy=read();	
	}
	sort(hi+1,hi+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(hi[i].xx==hi[i-1].xx && hi[i].yy==hi[i-1].yy)continue;
		if(hi[i].xx==hi[i].yy){
			continue;
		}else{
			cnt++;
		    e[cnt].to=hi[i].yy;
			e[cnt].nxt=head[hi[i].xx];
			head[hi[i].xx]=cnt;
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
	memset(head,0,(ans+1)*sizeof(int));
	memset(e,0,(m+1)*sizeof(edng));
	cnt=0;
	sort(hi+1,hi+m+1,cmpp);
	for(int i=1;i<=m;i++){
		
		if(color[hi[i].xx]==color[hi[i-1].xx] && color[hi[i].yy]==color[hi[i-1].yy])continue;
		if(color[hi[i].xx]==color[hi[i].yy]){
			continue;
		}else{
			cnt++;
		    e[cnt].to=color[hi[i].yy];
			e[cnt].nxt=head[color[hi[i].xx]];
			head[color[hi[i].xx]]=cnt;
		}
	}
	for(int i=1;i<=ans;i++){
		int l=dfs(i,0);
	}
//	
//	for(int i=1;i<=ans;i++){
//		cout<<AK[i]<<" ";
//	}
//	cout<<endl;
	cout<<Max<<endl<<hhh[Max];
	return 0;
}