可爱的tarjan模板题求调教喵～

rt

WA on 2 3 4 5 6 7 8

过样例。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define cerr ((ostream) 0)
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define gn(u, v) for (int v : G.G[u])
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tomin(x, y) ((x) = min((x), (y)))
#define tomax(x, y) ((x) = max((x), (y)))
#define ck(mask, i) (((mask) >> (i)) & 1)
#define pq priority_queue
#define FLG (cerr << "Alive!" << endl);

int MOD;

int qpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

struct Mint {
    int x;
    Mint() { x = 0; }
    Mint(const int _x) { x = _x % MOD; }
    friend Mint operator+(Mint x, Mint y) {
        int t = x.x + y.x;
        return (t >= MOD) ? (t - MOD) : t;
    }
    friend Mint operator-(Mint x, Mint y) {
        int t = x.x - y.x;
        return (t < 0) ? (t + MOD) : t;
    }
    friend Mint operator*(Mint x, Mint y) {
        return x.x * y.x % MOD;
    }
    friend Mint operator/(Mint x, Mint y) {
        return x.x * qpow(y.x, MOD - 2) % MOD;
    }
    friend Mint operator^(Mint& x, int y) {
        return Mint(qpow(x.x, y));
    }
    friend Mint& operator+=(Mint& x, Mint y) {
        return x = x + y;
    }
    friend Mint& operator-=(Mint& x, Mint y) {
        return x = x - y;
    }
    friend Mint& operator*=(Mint& x, Mint y) {
        return x = x * y;
    }
    friend Mint& operator/=(Mint& x, Mint y) {
        return x = x / y;
    }
    friend Mint& operator^=(Mint& x, int y) {
        return x = x ^ y;
    }
    friend ostream& operator<<(ostream& o, Mint y) {
        o << y.x;
        return o;
    }
    friend istream& operator>>(istream& i, Mint y) {
        i >> y.x;
        return i;
    }
    Mint& operator++() {
        x++;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }
    Mint operator++(signed) {
        x++;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }
    Mint& operator--() {
        x--;
        if (x < 0)
            x += MOD;
        return *this;
    }
    Mint operator--(signed) {
        x--;
        if (x < 0)
            x += MOD;
        return *this;
    }
    friend bool operator==(const Mint& x, const Mint &y) {
        return x.x == y.x;
    }
    friend bool operator!=(const Mint& x, const Mint &y) {
        return x.x == y.x;
    }
};

constexpr int MAXN = 1e5 + 5;
int n, m;
vi G[MAXN];

int scc_cnt, scc[MAXN], scc_sz[MAXN], low[MAXN], dfn[MAXN], num;
bool ins[MAXN];
stack<int> st;
void dfs(int u) {
    low[u] = dfn[u] = ++num;
    ins[u] = true;
    st.push(u);
    for (int v : G[u]) {
        if (!dfn[v]) {
            dfs(v);
            tomin(low[u], low[v]);
        } else if (ins[v]) {
            tomin(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_cnt++;
        int t;
        do {
            t = st.top();
            st.pop();
            ins[t] = false;
            scc[t] = scc_cnt;
            scc_sz[scc_cnt]++;
        } while (t != u);
    }
}

void tarjan() {
    rep(i, 1, n) {
        if (!dfn[i]) {
            dfs(i);
        }
    }
}

vi H[MAXN];

bool vis[MAXN];
int dis[MAXN], ans, ind[MAXN];
Mint cnt[MAXN];

void solve(int u) {
    vis[u] = true;
    if (H[u].empty()) {
        dis[u] = scc_sz[u];
        cnt[u] = 1;
        tomax(ans, dis[u]);
        return;
    }
    for (int v : H[u]) {
        if (!vis[v]) {
            solve(v);
        }
        if (dis[v] + scc_sz[u] > dis[u]) {
            dis[u] = dis[v] + scc_sz[u];
            cnt[u] = cnt[v];
        } else if (dis[v] + scc_sz[u] == dis[u]) {
            cnt[u] += cnt[v];
        }
        ans = max(ans, dis[u]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> MOD;
    rep(i, 1, n) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
    }

    tarjan();

    rep(u, 1, n) {
        for (int v : G[u]) {
            if (scc[v] != scc[u]) {
                H[scc[u]].pb(scc[v]);
                ind[scc[v]]++;
            }
        }
    }

    rep(i, 1, scc_cnt) {
        sort(all(H[i]));
        H[i].erase(unique(all(H[i])), H[i].end());
    }

    rep(i, 1, scc_cnt) {
        if (!vis[i] && !ind[i]) {
            solve(i);
        }
    }

    Mint ans2 = 0;
    rep(i, 1, scc_cnt) {
        if (dis[i] == ans) {
            ans2 += cnt[i];
        }
    } 

    cout << ans << endl << ans2 << endl;

    return 0;
}