#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3005;

int dis[MAXN][MAXN];
int dis2[MAXN][MAXN];

vector<int> G[MAXN];
vector<int> G2[MAXN];
vector<pair<int, int>> max_dis[MAXN];
vector<pair<int, int>> max_dis2[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G2[y].push_back(x);
    }
    memset(dis, 127 / 3, sizeof(dis));
    memset(dis2, 127 / 3, sizeof(dis2));
    for (int i = 1; i <= n; i++) {
        queue<int> Q;
        dis[i][i] = 0;
        Q.push(i);
        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();
            for (auto nx : G[cur]) {
                if (dis[i][cur] + 1 < dis[i][nx]) {
                    dis[i][nx] = dis[i][cur] + 1;
                    Q.push(nx);
                }
            }
        }
        dis2[i][i] = 0;
        Q.push(i);
        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();
            for (auto nx : G2[cur]) {
                if (dis2[i][cur] + 1 < dis2[i][nx]) {
                    dis2[i][nx] = dis2[i][cur] + 1;
                    Q.push(nx);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j || dis[i][j] == dis[0][0])
                continue;
            max_dis[i].push_back(make_pair(-dis[i][j], j));
        }
        for (int j = 1; j <= n; j++) {
            if (i == j || dis2[i][j] == dis[0][0])
                continue;
            max_dis2[i].push_back(make_pair(-dis2[i][j], j));
        }
        sort(max_dis[i].begin(), max_dis[i].end());
        sort(max_dis2[i].begin(), max_dis2[i].end());
    }
    int ans = 0;
    int min_b = -1;
    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            if (b == c || dis[b][c] == dis[0][0])
                continue;
            vector<int> A, D;
            for (int i = 0; i < min(2, (int)max_dis2[b].size()); i++) {
                A.push_back(max_dis2[b][i].second);
            }
            for (int i = 0; i < min(2, (int)max_dis[c].size()); i++) {
                D.push_back(max_dis[c][i].second);
            }
            for (auto a : A) {
                for (auto d : D) {
                    if (a == b || a == c || a == d || d == b || d == c)
                        continue;
                    int new_ans = dis[a][b] + dis[b][c] + dis[c][d];
                    if (new_ans > ans) {
                        ans = new_ans;
                        min_b = b;
                    }
                }
            }
        }
    }
    cout << ans << " " << min_b << endl;
    return 0;
}