OI XXI - raj

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

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 500 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

constexpr int INF = 1e9;

namespace seg {

int d[4 * sizik];
void init(int v, int tl, int tr) {
}

void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        d[v] = std::max(d[v], x);
        return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, std::min(r, tm), x);
    update(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, x);
}

int query(int v, int tl, int tr, int x) {
    if (tl == tr) {
        return d[v];
    } else {
        int tm = (tl + tr) / 2;
        if (x <= tm) {
            return std::max(d[v], query(2 * v, tl, tm, x));
        } else {
            return std::max(d[v], query(2 * v + 1, tm + 1, tr, x));
        }
    }
}

} // namespace seg

ar<int, sizik> num, rev_num, dp_gora, dp_dol, pref, suff;
ar<int, sizik> in_deg;
int n, m;

ar<std::vector<int>, sizik> kra, kra_num, kra_num_trans;

void topo_sort() {
    for (int i = 1; i <= n; i++) {
        for (const auto& a : kra[i]) {
            in_deg[a]++;
        }
    }
    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_deg[i] == 0) q.push(i);
    }

    int curr = 1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();

        num[v] = curr;
        rev_num[curr] = v;
        curr++;

        for (const auto& a : kra[v]) {
            if (--in_deg[a] == 0) {
                q.push(a);
            }
        }
    }
}

int get_ans(int v) {
    return std::max({pref[v - 1], suff[v + 1], seg::query(1, 1, n, v)});
}

void solve() {
    std::cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        kra[a].push_back(b);
    }

    topo_sort();

    for (int i = 1; i <= n; i++) {
        for (const auto& a : kra[i]) {
            kra_num[num[i]].push_back(num[a]);
            kra_num_trans[num[a]].push_back(num[i]);
        }
    }
    for (int i = n; i >= 1; i--) {
        dp_dol[i] = 0;
        for (const auto& a : kra_num[i]) {
            dp_dol[i] = std::max(dp_dol[i], dp_dol[a] + 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        dp_gora[i] = 0;
        for (const auto& a : kra_num_trans[i]) {
            dp_gora[i] = std::max(dp_gora[i], dp_gora[a] + 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        pref[i] = std::max(pref[i - 1], dp_gora[i]);
    }
    for (int i = n; i >= 1; i--) {
        suff[i] = std::max(suff[i + 1], dp_dol[i]);
    }

    auto len = [](int a, int b) -> int { return dp_gora[a] + dp_dol[b] + 1; };

    for (int i = 1; i <= n; i++) {
        for (const auto& a : kra_num[i]) {
            seg::update(1, 1, n, i + 1, a - 1, len(i, a));
        }
    }

    int ans = INF, ans_v = -1;
    for (int i = 1; i <= n; i++) {
        int x = get_ans(i);
        if (x < ans) {
            ans = x;
            ans_v = rev_num[i];
        }
    }

    std::cout << ans_v << ' ' << ans << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}