1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

namespace fast_io {
    ...
}using namespace fast_io;

const int MAXN = 110000,MAXM = 2100000;

struct stack{
    int num[MAXN],topnum;
    stack(){topnum = 0;}
    void pop(){topnum--;}
    int top(){return num[topnum-1];}
    void push(int val){num[topnum++] = val;}
    bool empty(){return topnum != 0;}
}a;

int n,m,ecnt = 1,X;

int fir[MAXN];
int cnt = 1,cnum = 0;
int low[MAXN],dfn[MAXN],siz[MAXN];
int col[MAXN];
int instack[MAXN];

struct Edge{
    int from,to,nex;
    bool operator < (Edge a)const{
        if(from == a.from)
            return to < a.to;
        return from < a.from;
    }
}edge[MAXM];

void addedge(int a,int b){
    edge[ecnt].from = a,edge[ecnt].to = b;
    edge[ecnt].nex = fir[a];fir[a] = ecnt++;
}

void dfs(int nown){
    low[nown] = dfn[nown] = cnt++;
    instack[nown] = 1;a.push(nown);
    for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
        int v = edge[nowe].to;
        if(dfn[v] == 0)
            dfs(v),low[nown] = min(low[v],low[nown]);
        else if(instack[v] == 1)
            low[nown] = min(dfn[v],low[nown]);
    }
    if(low[nown] == dfn[nown]){
        cnum++;int j = -1;
        do{
            j = a.top();a.pop();
            instack[j] = 0;
            col[j] = cnum;
            siz[cnum]++;
        }while(j!=nown);
    }
}

void tarjan(){
    for(int i = 1;i<=n;i++)
        if(dfn[i] == 0)
            dfs(i);
    for(int i = 1;i<=m;i++){
        edge[i].from = col[edge[i].from];
        edge[i].to = col[edge[i].to];
    }
    memset(fir,0,sizeof(fir));
    //去重！！！
    sort(edge+1,edge+m+1);
    int lastu = 0,lastv = 0;
    for(int i = 1;i<=m;i++){
        int u = edge[i].from,v = edge[i].to;
        if(u!=v&&(!(u==lastu&&v==lastv)))
            addedge(u,v);
        lastu = u,lastv = v;
    }
}

int dp[MAXN],num[MAXN];

void dfs2(int nown){
    dp[nown] = siz[nown],num[nown] = 1;
    for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
        int v = edge[nowe].to;
        if(dp[v] == 0) dfs2(v);
        if(dp[nown] < dp[v] + siz[nown])
            dp[nown] = dp[v] + siz[nown],num[nown] = num[v];
        else if(dp[nown] == dp[v] + siz[nown])
            num[nown] += num[v], num[nown] %= X;
    }
}

void solve(){
    for(int i = 1;i<=cnum;i++)
        if(num[i] == 0)
            dfs2(i);
    int ans1 = 0,ans2 = 0;
    for(int i = 1;i<=cnum;i++){
        if(dp[i] > ans1) ans1 = dp[i],ans2 = num[i];
        else if(dp[i] == ans1) ans2 += num[i],ans2 %=X;
    }
    print(ans1),print('\n'),print(ans2),print('\n');
}

void init(){
    read(n),read(m),read(X);
    int a,b;
    for(int i = 1;i<=m;i++){
        read(a),read(b);
        addedge(a,b);
    }
}

int main(){
    init();
    tarjan();
    solve();
    flush();
    return 0;
}