OI XXI - raj (Alt1)

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

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct Edge {
    int pa, pb, val;
};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        indeg[b]++;
    }

    vector<int> order;
    order.reserve(n);
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }

    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i)
        pos[order[i]] = i + 1;

    vector<int> bck(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int u = order[i];
        for (int v : adj[u])
            if (bck[v] < bck[u] + 1) bck[v] = bck[u] + 1;
    }

    vector<int> fwd(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        for (int v : adj[u])
            if (fwd[u] < fwd[v] + 1) fwd[u] = fwd[v] + 1;
    }

    vector<int> preMax(n + 2, 0), sufMax(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        int node = order[i - 1];
        preMax[i] = max(preMax[i - 1], bck[node]);
    }
    for (int i = n; i >= 1; --i) {
        int node = order[i - 1];
        sufMax[i] = max(sufMax[i + 1], fwd[node]);
    }

    vector<Edge> edges;
    edges.reserve(m);
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            int pa = pos[u];
            int pb = pos[v];
            int val = bck[u] + 1 + fwd[v];
            edges.push_back({pa, pb, val});
        }
    }
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.pa < b.pa; });

    int size = 1;
    while (size < n)
        size <<= 1;
    vector<int> seg(2 * size, -1);

    auto update = [&](int p, int val) {
        p += size;
        if (seg[p] < val) seg[p] = val;
        for (p >>= 1; p; p >>= 1)
            seg[p] = max(seg[p * 2], seg[p * 2 + 1]);
    };

    auto query = [&](int l, int r) -> int {
        if (l > r) return -1;
        l += size;
        r += size;
        int res = -1;
        while (l <= r) {
            if (l & 1) {
                if (res < seg[l]) res = seg[l];
                l++;
            }
            if (!(r & 1)) {
                if (res < seg[r]) res = seg[r];
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    };

    vector<int> bestLR(n + 1, 0);
    int ei = 0;
    int E = edges.size();
    for (int i = 1; i <= n; ++i) {
        while (ei < E && edges[ei].pa < i) {
            update(edges[ei].pb - 1, edges[ei].val);
            ei++;
        }
        int q = (i + 1 <= n) ? query(i + 1 - 1, n - 1) : -1;
        bestLR[i] = max(0, q);
    }

    int best_node = -1, best_len = 1e9;
    for (int i = 1; i <= n; ++i) {
        int node = order[i - 1];
        int left = preMax[i - 1];
        int right = sufMax[i + 1];
        int cross = bestLR[i];
        int cur = max({left, right, cross});
        if (cur < best_len) {
            best_len = cur;
            best_node = node;
        } else if (cur == best_len && node < best_node) {
            best_node = node;
        }
    }

    printf("%d %d\n", best_node, best_len);
    return 0;
}