OI XXI - raj (Alt2)

// https://szkopul.edu.pl/problemset/problem/orur2kPvWQR0LzMXXoP6pCat/site/?key=statement

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

const int N = 5e5 + 5;
int n, m;
vector<int> e[N], e2[N];
int a[N], deg[N], tot;
int f[N], g[N];
int pre[N], suf[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].pb(v);
        e2[v].pb(u);
        deg[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int f = q.front();
        q.pop();
        a[++tot] = f;
        for (int i : e[f]) {
            deg[i]--;
            if (!deg[i]) q.push(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j : e[a[i]]) {
            f[j] = max(f[j], f[a[i]] + 1);
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j : e2[a[i]]) {
            g[j] = max(g[j], g[a[i]] + 1);
        }
    }
    for (int i = 1; i <= n; i++)
        pre[a[i]] = max(pre[a[i - 1]], f[a[i]]);
    for (int i = n; i >= 1; i--)
        suf[a[i]] = max(suf[a[i + 1]], g[a[i]]);
    multiset<int> st;
    int mn = 1e9, id = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        for (int j : e2[a[i]])
            st.erase(st.find(f[j] + g[a[i]] + 1));
        if (st.empty())
            x = 0;
        else
            x = *(--st.end());
        x = max({x, pre[a[i - 1]], suf[a[i + 1]]});
        if (x < mn) mn = x, id = a[i];
        for (int j : e[a[i]])
            st.insert(f[a[i]] + g[j] + 1);
    }
    cout << id << ' ' << mn;
    return 0;
}