#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=100005; const int M=2000005; const LL P=1000007; // hash code int n, m, mod; int h[N], hs[N], E=0; // 图和导出图 int dfn[N], low[N], ts=0; bool vis[N]; stack<int> st; int id[N], scc_cnt=0, sz[N]; // scc 数组 int f[N], g[N]; struct Edge{ int v, ne; }e[M]; void add(int h[], int a, int b){ // 建图, 根据参数不同建立普通图或者导出图 e[E].v=b; e[E].ne=h[a]; h[a]=E++; } void tarjan(int u){ dfn[u]=low[u]=ts++; st.push(u); vis[u]=true; for(int i=h[u]; ~i; i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ // 树枝边 tarjan(v); low[u]=min(low[u], low[v]); } else if(vis[v]){ // 横叉边或者后向边 low[u]=min(low[u], dfn[v]); } } if(dfn[u]==low[u]){ // 当前节点为scc起点 ++scc_cnt; int j; do{ j=st.top(); st.pop(); vis[j]=false; id[j]=scc_cnt; sz[scc_cnt]++; }while(j!=u); } } int main(){ memset(h, -1, sizeof h); memset(hs, -1, sizeof hs); cin>>n>>m>>mod; while(m--){ int a, b; cin>>a>>b; add(h, a, b); } // 找出所有scc for(int i=1; i<=n; ++i) if(!dfn[i]) tarjan(i); // 缩点建立导出图 unordered_set<LL> rec; for(int i=1; i<=n; ++i){ for(int j=h[i]; ~j; j=e[j].ne){ int v=e[j].v; int a=id[i], b=id[v]; LL hash=a*P+b; if(a!=b && !rec.count(hash)){ add(hs, a, b); rec.insert(hash); } } } for(int i=scc_cnt; i; --i){ if(!f[i]){ f[i]=sz[i]; g[i]=1; } for(int j=hs[i]; ~j; j=e[j].ne){ int v=e[j].v; if(f[v]<f[i]+sz[v]){ f[v]=f[i]+sz[v]; g[v]=g[i]; } else if(f[v]==f[i]+sz[v]) g[v]=(g[v]+g[i])%mod; } } int maxf=0, sum=0; for(int i=1; i<=scc_cnt; ++i){ if(f[i]>maxf){maxf=f[i]; sum=g[i];} else if(f[i]==maxf) sum=(sum+g[i])%mod; } cout<<maxf<<endl; cout<<sum<<endl; return 0; }