题目描述

题目译自 XXI Olimpiada Informatyczna — II etap Rajd

字节城即将迎来一年一度的自行车赛。当地自行车手个个是长距离耐力好手。然而，与自行车手素有恩怨的摩托车手团体决定搞破坏，誓要让这场盛事泡汤！

字节城有 $n$ 个路口，通过单向街道相连。有趣的是，街道网络无环：若从路口 $u$ 可达 $v$，则绝无路径从 $v$ 回到 $u$。自行车赛的路线将沿着这些街道展开。摩托车手计划在比赛日清晨，骑着锃亮的摩托车霸占某个路口，彻底封锁它。虽然自行车协会会迅速调整路线，但新路线可能较短，让自行车手无法尽展耐力。这正是摩托车手的阴谋：他们要挑一个路口封锁，让绕过它的最长路线尽可能短。

请你编写程序，帮摩托车手找出最佳的封锁路口！

输入格式

输入第一行包含两个整数 $n, m$ $(2 \leq n \leq 500000, 1 \leq m \leq 1000000)$，分别表示路口数和街道数。路口编号为 $1$ 到 $n$。

接下来的 $m$ 行描述路网，每行两个整数 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示从路口 $a_{i}$ 到 $b_{i}$ 有一条单向街道。

输出格式

输出一行，包含两个整数：第一个表示摩托车手应封锁的路口编号，第二个表示绕过该路口后自行车手能通过的最长路线的街道数。若有多解，输出任意一解即可。

6 5
1 3
1 4
3 6
3 4
4 5

1 2

附加样例

1. $n=10, m=9$，路网为一条路径，最佳封锁点在中间；
2. $n=100, m=4950$，存在所有从编号较小到较大路口的街道；
3. $n=500000, m=749999$，从路口 $i$ 有街道到 $i-1$（若 $i \geq 2$）及 $\frac{i}{2}$（若 $2 \mid i$）。

数据范围与提示

对于 $33\%$ 的数据，每条街道满足 $a_{i} < b_{i}$。