OI XXI - raj (Iterative)

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

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int INF = 1e9;

int BASE = 1;
vector<int> tree;

void update_max(int l, int r, int val) {
    if (l > r) return;
    l += BASE;
    r += BASE;
    tree[l] = max(tree[l], val);
    tree[r] = max(tree[r], val);
    while (l / 2 != r / 2) {
        if (l % 2 == 0) tree[l + 1] = max(tree[l + 1], val);
        if (r % 2 == 1) tree[r - 1] = max(tree[r - 1], val);
        l /= 2;
        r /= 2;
    }
}

void push_down() {
    for (int i = 1; i < BASE; ++i) {
        tree[2 * i] = max(tree[2 * i], tree[i]);
        tree[2 * i + 1] = max(tree[2 * i + 1], tree[i]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> edges(m);
    vector<vector<int>> adj(n + 1);
    vector<int> in_degree(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        cin >> edges[i].first >> edges[i].second;
        adj[edges[i].first].push_back(edges[i].second);
        in_degree[edges[i].second]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo_order;
    topo_order.reserve(n);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);

        for (int v : adj[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    vector<int> topo_pos(n + 1);
    vector<int> orig_node(n + 1);
    for (int i = 0; i < n; ++i) {
        topo_pos[topo_order[i]] = i + 1;
        orig_node[i + 1] = topo_order[i];
    }

    vector<vector<int>> g(n + 1);
    vector<vector<int>> rev_g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u = topo_pos[edges[i].first];
        int v = topo_pos[edges[i].second];
        g[u].push_back(v);
        rev_g[v].push_back(u);
    }

    vector<int> longestEnd(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int prev : rev_g[i]) {
            longestEnd[i] = max(longestEnd[i], longestEnd[prev] + 1);
        }
    }

    vector<int> longestStart(n + 1, 0);
    for (int i = n; i >= 1; --i) {
        for (int next : g[i]) {
            longestStart[i] = max(longestStart[i], longestStart[next] + 1);
        }
    }

    vector<int> longestBefore(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        longestBefore[i] = max(longestBefore[i - 1], longestEnd[i]);
    }

    vector<int> longestAfter(n + 2, 0);
    for (int i = n; i >= 1; --i) {
        longestAfter[i] = max(longestAfter[i + 1], longestStart[i]);
    }

    while (BASE <= n + 1)
        BASE *= 2;
    tree.assign(2 * BASE, 0);

    for (int u = 1; u <= n; ++u) {
        for (int v : g[u]) {
            if (u + 1 <= v - 1) {
                int path_len = longestEnd[u] + 1 + longestStart[v];
                update_max(u + 1, v - 1, path_len);
            }
        }
    }

    push_down();

    int best_node = 1;
    int min_longest_path = INF;

    for (int i = 1; i <= n; ++i) {
        int bypass = tree[BASE + i];
        int before = longestBefore[i - 1];
        int after = longestAfter[i + 1];

        int current_max = max({before, after, bypass});

        if (current_max < min_longest_path) {
            min_longest_path = current_max;
            best_node = orig_node[i];
        }
    }

    cout << best_node << " " << min_longest_path << "\n";

    return 0;
}