OI XXI - raj (Alt4)

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

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

namespace Cherry {
const int N = 5e5 + 5;
int n, m, cnt, st, en, ans, res;
int rd[N], rd2[N], num[N], S[N], T[N], q[N];
vector<int> e[N], e2[N];

struct Stack {
    priority_queue<int> q1, q2;
    void push(int x) { q1.push(x); }
    void pop(int x) { q2.push(x); }
    int size() {
        while (!q1.empty() && !q2.empty() && q1.top() == q2.top())
            q1.pop(), q2.pop();

        return q1.size();
    }
    int top() { return q1.top(); }
} s, t, crs;

void Topu() {
    st = 1, en = 0;

    for (int i = 1; i <= n; i++) {
        if (!rd[i]) q[++en] = i;
    }

    while (st <= en) {
        int x = q[st++];
        num[++cnt] = x;

        for (auto y : e[x]) {
            rd[y]--;
            S[y] = max(S[y], S[x] + 1);

            if (!rd[y]) q[++en] = y;
        }
    }
}
void Topu2() {
    st = 1, en = 0;

    for (int i = 1; i <= n; i++) {
        if (!rd2[i]) q[++en] = i;
    }

    while (st <= en) {
        int x = q[st++];

        for (auto y : e2[x]) {
            rd2[y]--;
            T[y] = max(T[y], T[x] + 1);

            if (!rd2[y]) q[++en] = y;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e2[y].push_back(x);
        rd[y]++, rd2[x]++;
    }

    Topu(), Topu2();
    ans = 1e9;

    for (int i = 1; i <= n; i++)
        t.push(T[i]);

    for (int i = 1; i <= n; i++) {
        int x = num[i], now = 0;
        t.pop(T[x]);

        for (auto y : e2[x])
            crs.pop(S[y] + T[x] + 1);

        if (s.size()) now = max(now, s.top());

        if (t.size()) now = max(now, t.top());

        if (crs.size()) now = max(now, crs.top());

        if (now < ans) ans = now, res = x;

        s.push(S[x]);

        for (auto y : e[x])
            crs.push(S[x] + T[y] + 1);
    }

    printf("%d %d\n", res, ans);

    return 0;
}
} // namespace Cherry

int main() {
    Cherry::main();

    return 0;
}