代码如下

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5 + 5; // 最大点数
int MOD; // 取模
int n, m;             // 节点数和边数

vector<int> graph[N];  // 原图的邻接表
vector<int> dag[N];    // 缩点后的DAG图
int dfn[N], low[N], scc[N], sccSize[N], d[N], ways[N]; // Tarjan和动态规划需要的数组
bool inStack[N];       // 判断点是否在栈中
stack<int> st;         // Tarjan算法的栈
int timestamp = 0, sccCount = 0; // 时间戳和强连通分量计数

// Tarjan算法：寻找强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    st.push(u);
    inStack[u] = true;
    for (int v : graph[u]) {
        if (!dfn[v]) { // 未访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) { // 在当前栈中
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) { // 找到一个强连通分量
        sccCount++;
        int node;
        do {
            node = st.top();
            st.pop();
            inStack[node] = false;
            scc[node] = sccCount; // 记录点所属的SCC编号
            sccSize[sccCount]++;  // 统计SCC的大小
        } while (node != u);
    }
}

// 在DAG上进行深度优先搜索，寻找最长路径，并统计方案数
int dfs(int u) {
    if (d[u]) return d[u]; // 如果已经计算过，直接返回
    d[u] = sccSize[u]; // 起始点的路径长度
    ways[u] = 1;       // 起始点的方案数为 1
    for (int v : dag[u]) {
        int len = dfs(v) + sccSize[u]; // 计算路径长度
        if (len > d[u]) {
            d[u] = len;
            ways[u] = ways[v]; // 更新方案数
        } else if (len == d[u]) {
            ways[u] = (ways[u] + ways[v]) % MOD; // 累加方案数，取模
        }
    }
    return d[u];
}

int main() {
    cin >> n >> m >>MOD;

    // 读取图的输入（邻接表存储）
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    // 使用Tarjan算法寻找强连通分量
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 构建缩点后的DAG
    for (int u = 1; u <= n; u++) {
        for (int v : graph[u]) {
            if (scc[u] != scc[v]) { // 不在同一个SCC中才加边
                dag[scc[u]].push_back(scc[v]);
            }
        }
    }

    // 对DAG的边去重（最平凡的方式实现）
    for (int i = 1; i <= sccCount; i++) {
        // 排序确保重复元素相邻
        sort(dag[i].begin(), dag[i].end());

        // 手动去重：保留唯一元素
        vector<int> uniqueEdges;
        for (int j = 0; j < dag[i].size(); j++) {
            if (j == 0 || dag[i][j] != dag[i][j - 1]) { // 和前一个元素不同才保留
                uniqueEdges.push_back(dag[i][j]);
            }
        }
        dag[i] = uniqueEdges; // 将去重后的结果赋回原来的邻接表
    }

    // 在DAG上计算最长路径及方案数
    int maxLength = 0, totalWays = 0;
    memset(d, 0, sizeof(d));
    memset(ways, 0, sizeof(ways));
    for (int i = 1; i <= sccCount; i++) {
        int len = dfs(i); // 计算每个 SCC 的最长路径
        if (len > maxLength) {
            maxLength = len;
            totalWays = ways[i]; // 更新方案数
        } else if (len == maxLength) {
            totalWays = (totalWays + ways[i]) % MOD; // 累加方案数，取模
        }
    }

    // 输出最长路径长度和方案数
    cout << maxLength << endl;
    cout << totalWays << endl;
    return 0;
}