OI XXI - raj (Dsu)

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

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

using namespace std;

struct DisjointSetUnion {
    vector<int> parent;
    DisjointSetUnion(int n) {
        parent.resize(n + 2);
        for (int i = 1; i <= n + 1; ++i) {
            parent[i] = i;
        }
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
};

struct Edge {
    int u, v;
};

struct IntervalList {
    struct Node {
        int l, r;
        int nxt;
    };
    vector<int> head;
    vector<Node> nodes;

    IntervalList(int max_val, int max_intervals) {
        head.assign(max_val + 1, -1);
        nodes.reserve(max_intervals);
    }

    void add(int val, int l, int r) {
        if (l > r) return;
        nodes.push_back({l, r, head[val]});
        head[val] = (int)nodes.size() - 1;
    }
};

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

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

    vector<Edge> 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].u >> edges[i].v;
        adj[edges[i].u].push_back(edges[i].v);
        in_degree[edges[i].v]++;
    }

    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);
    vector<int> topo_pos(n + 1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        topo_pos[u] = (int)topo_order.size();
        for (int v : adj[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

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

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

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

    IntervalList valIntervals(n, 2 * n + m);

    for (int w = 1; w < n; ++w) {
        valIntervals.add(longestEnd[w], w + 1, n);
    }

    for (int w = 2; w <= n; ++w) {
        valIntervals.add(longestStart[w], 1, w - 1);
    }

    for (int u = 1; u <= n; ++u) {
        for (int w : topo_adj[u]) {
            if (u + 1 <= w - 1) {
                int len = longestEnd[u] + 1 + longestStart[w];
                valIntervals.add(len, u + 1, w - 1);
            }
        }
    }

    DisjointSetUnion dsu(n);
    int covered_count = 0;
    int best_vertex = topo_order[0];
    int best_len = 0;

    for (int l = n; l >= 0; --l) {
        int candidate = dsu.find(1);
        if (candidate <= n) {
            best_vertex = topo_order[candidate - 1];
            best_len = l;
        }

        for (int e = valIntervals.head[l]; e != -1; e = valIntervals.nodes[e].nxt) {
            int left = valIntervals.nodes[e].l;
            int right = valIntervals.nodes[e].r;

            int curr = dsu.find(left);
            while (curr <= right) {
                covered_count++;
                dsu.parent[curr] = dsu.find(curr + 1);
                curr = dsu.parent[curr];
            }
        }

        if (covered_count == n) {
            break;
        }
    }

    cout << best_vertex << " " << best_len << "\n";

    return 0;
}