#1115. 2-11G. JM的玄学旅社

在这为期总共4周的ACM小学期里，qz被投喂了太多的解不出题的人，他感觉撑得慌。为了更好地消化，他决定在渡渡鸟王国进行一次惬意的旅行。

渡渡鸟王国有 $n$ 座城市，城市的编号为 $1, 2, ..., n$ 。其间有 $m$ 条距离为 $1$ 的单向道路，每条道路连接两座不同的城市。

在收到上面这条垃圾短信后，qz去JM旅行社预定了四倍满豪华旅行套餐。这意味着，qz需要选择 $4$ 座互不相同的城市 $a,\ b,\ c,\ d$ ，并沿着 $a \rightarrow b \rightarrow c \rightarrow d$ 的路径完成他的旅行。不需要从 $d$ 返回 $a$ 。并且，在上述过程中，在从某一城市 $u$ 前往另一城市 $v$ 时，qz必须沿着任意一条从 $u$ 到 $v$ 的最短路径行走。也就是说，qz需要走过从 $a$ 到 $b$ 的最短路径、走过从 $b$ 到 $c$ 的最短路径、走过从 $c$ 到 $d$ 的最短路径，完成他的旅行。

为了尽可能地消化食物，qz希望选择城市 $a,\ b,\ c,\ d$ 使得他在旅行中途经的总距离最长。注意，在旅行过程中可能可以重复访问某一城市，只要遵循前文所述的旅行规则即可。现在你需要告诉qz这个最长的旅行总距离是多少，否则qz不介意吃得更撑一点。

第一行两个正整数 $n$ 和 $m$ 。

接下来 $m$ 行，每行两个正整数 $u,\ v$ 表示一条从 $u$ 到 $v$ 的单向道路。输入保证 $u \ne v$ 。

输出一行两个正整数 $dist$ 和 $b$ ，表示可能的最长的旅行总距离，以及你为qz选择的第二座城市的编号。如果存在多种最长方案，则输出第二座城市的可能的最小编号。

样例输入

8 9
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 8
8 5

样例输出

13 1

$4 \le n \le 3000$

$3 \le m \le 5000$

不保证题给的图一定强连通，但一定有解。

Hint

对于样例，最长方案为 $A = 2,\ B = 1,\ C = 8,\ D = 7$ ，最长距离为 $dist(2,\ 1) + dist(1,\ 8) + dist(8,\ 7) = 3 + 7 + 3 = 13$ 。