Byteburg 即将举办一年一度的自行车拉力赛。Byteburg 的骑手们天生擅长长距离骑行。当地摩托车手代表与骑手们积怨已久，决定破坏这次活动。

Byteburg 有 $n$ 个交叉路口，由单向街道连接。奇怪的是，街道网络中不存在环路——如果可以从交叉路口 $u$ 骑行到交叉路口 $v$，那么绝对不可能从 $v$ 骑行到 $u$。

拉力赛的路线将穿过 Byteburg 的街道。摩托车手计划在比赛当天的清晨骑着他们轰鸣的机器前往某一个交叉路口并将其完全封锁。自行车协会随后当然会确定一条替代路线，但可能会出现这种情况：这条新路线相对较短，骑手们因此无法展现他们非凡的耐力。显然，这就是摩托车手的计划——他们打算封锁这样一个交叉路口，使得不经过该路口的最长路线尽可能短。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500\,000$, $1 \le m \le 1\,000\,000$)，由一个空格分隔，分别表示 Byteburg 的交叉路口数量和街道数量。交叉路口编号为 $1$ 到 $n$。接下来的 $m$ 行描述了街道网络：其中第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ ($1 \le a_{i}, b_{i} \le n$, $a_{i} \neq b_{i}$)，由一个空格分隔，表示有一条从交叉路口 $a_{i}$ 到 $b_{i}$ 的单向街道。

输出格式

标准输出的第一行应包含两个由空格分隔的整数。第一个整数是摩托车手应该封锁的交叉路口编号，第二个整数是骑手们在封锁后能够骑行的最长街道数量。如果存在多个解，你的程序可以任意选择其中一个。

样例

输入 1

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

输出 1

1 2