1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define FOR(x,l,r) for(int x=l;x<=r;++x)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int INF = 1000000007;
const int maxn = 500005;
const int maxm = 1000005*2;

int getint() {
	int r = 0; bool b = true; char c = getchar();
	while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
	while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
	if (b) return r;
	return -r;
}

queue<int> Q;
int n, m, ans = INF, pos, S, T;

struct Graph_type {
	int cnte, h[maxn], dp[maxn], rd[maxn];
	struct edge_type { int to, next; } edge[maxm];
	inline void ins(int x, int y) {
		edge[++cnte].to = y;
		edge[cnte].next = h[x];
		h[x] = cnte;
		++rd[y];
	}
	inline void solve() {
		int now;
		if (rd[S] == 0) Q.push(S);
		if (rd[T] == 0) Q.push(T);
		while (!Q.empty()) {
			now = Q.front(); Q.pop();
			for (int i = h[now]; i; i = edge[i].next) {
				dp[edge[i].to] = max(dp[edge[i].to], dp[now] + 1);
				if (--rd[edge[i].to] == 0) Q.push(edge[i].to);
			}
		}
	}
	void work();
} G1, G2, G3;

bool del[maxn];

void Graph_type::work() {
	static priority_queue<pair<int, int> > H;
	Q.push(S);
	int now, tmp;
	while (!Q.empty()) {
		now = Q.front(); Q.pop(); del[now] = true;
		tmp = max(G1.dp[now] - 2, G2.dp[now] - 2);
		while (!H.empty() && del[H.top().second]) H.pop();
		if (!H.empty()) tmp = max(tmp, H.top().first);
		if (ans > tmp && now != S && now != T) { ans = tmp; pos = now; }
		for (int i = h[now]; i; i = edge[i].next) {
			tmp = edge[i].to;
			H.push(make_pair(G1.dp[now] - 1 + G2.dp[tmp], tmp));
			if (--rd[tmp] == 0) Q.push(tmp);
		}
	}
}

int main() {
	n = getint(); m = getint();
	int x, y;
	FOR(i,1,m) {
		x = getint(); y = getint();
		G1.ins(x, y); G2.ins(y, x); G3.ins(x, y);
	}
	S = n+1; T = S+1;
	FOR(i,1,n) {
		//if (G1.rd[i] == 0) { 
		G1.ins(S, i); G2.ins(i, S); G3.ins(S, i);
		// }
		//if (G2.rd[i] == 0) { 
		G1.ins(i, T); G2.ins(T, i); G3.ins(i, T);
		// }
	}
	G1.solve(); G2.solve(); G3.work();
	if (ans < 0) {ans = 0; pos = 1;}
	printf("%d %d", pos, ans);
	return 0;
}