#include<bits/stdc++.h>
#define MAXN 100050
#define MAXM 1000050
using namespace std;
int low[MAXN],dfn[MAXN],sta[MAXN],rd[MAXN];
int tp,cnt,num;
bool ins[MAXN];
queue<int> q;
long long siz[MAXN];
int col[MAXN];
long long f[MAXN],g[MAXN];
int n,m;
long long p;
struct Edge{
int to,nxt;
}edge[MAXM];
int head[MAXN],ectr;
void addedge(int from,int to){
ectr++;
edge[ectr].to = to;
edge[ectr].nxt = head[from];
head[from] = ectr;
}
struct Data{
int a,b;
}data[MAXM];
struct DATA{
int a,b;
}DA[MAXM];
bool cmp(DATA x,DATA y){
if(x.a != y.a) return x.a<y.a;
else return x.b<y.b;
}
void tarjan(int x){
dfn[x] = low[x] = ++num;
sta[++tp] = x;
ins[x] = true;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
}
else if (ins[y]){
low[x] = min(low[x] ,dfn[y]);
}
}
if(dfn[x] == low[x] ){
++cnt;
int y=0;
do{
y=sta[tp--];
col[y] = cnt;
siz[cnt] ++;
ins[y] = false;
}while (y!=x);
}
}
void topo(){
for(int i=1;i<=cnt;i++){
if( !rd[i] ) q.push(i),f[i] = siz[i],g[i]=1;
}
while (!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(!--rd[y]) q.push(y);
if(f[x] + siz[y] > f[y] ){
f[y] = siz[y] + f[x];
g[y] = g[x];
g[y] %=p;
}
else if(f[x] + siz[y] == f[y]){
g[y] += g[x] ;
g[y] %= p;
}
}
}
}
int main(){
cin>>n>>m;
cin>>p;
for(int i=1;i<=m;i++){
scanf("%d%d",&data[i].a,&data[i].b);
addedge(data[i].a,data[i].b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++) head[i] = 0;
ectr=0;
for(int i=1;i<=m;i++){
int x= col[data[i].a];
int y= col[data[i].b];
if(x==y) continue;
DA[i].a=x;
DA[i].b=y;
}
sort (DA +1,DA+1+m,cmp);
int prex=0,prey=0;
for(int i=1;i<=m;i++){
int x=DA[i].a;
int y=DA[i].b;
if(x==prex && y==prey) continue;
if(x!=y) addedge(x,y),rd[y]++,prex=x,prey=y;
}
topo();
long long ans1=0,ans2=0;
for(int i=1;i<=cnt;i++){
ans1=max(ans1,f[i]);
}
for(int i=1;i<=cnt;i++){
if(f[i]==ans1){
ans2+=g[i];
}
}
cout<<ans1<<endl<<ans2;
return 0;
}
by Hydra_Shouko @ 2019-03-21 18:02:02
@[SIN_XIII](/space/show?uid=131920) 您是不是漏取模了
by hongzy @ 2019-03-30 14:28:19
@[Hydra_Shouko](/user/131920) 取模要在中间一直取
by orzws @ 2021-10-18 21:48:48