图上删点

题目描述

给定一张有向无环图（$DAG$），点数为$n$，边数为$m$。

你可以在图中删去一个点，并且删去与该点相连的边，并且得到剩下部分最长路的长度。其中一条路径的长度被定义为这条路径经过的边数。

你需要求出$n$个删点方案中，剩下部分最长路长度的最小值，以及对应的其中一种删点方案。

输入格式

第一行包含两个正整数$n$，$m$，表示原$DAG$的点数和边数。$DAG$的点被编号为$1$到$n$。

接下来$m$行，每行包含两个正整数$u$，$v$，表示一条有向边$u \to v$。

输出格式

输出仅有一行，包含两个整数$ans_0$，$ans_1$。

$ans_0$表示需要删去的点的编号，$ans_1$表示最短的最长路长度。

本题有$Special$ $Judge$，如果有多种方案使最长路最短，只要输出任意一个合法的$ans_0$。

数据范围与提示

本题采用子任务捆绑测试。对于每个子任务，你需要通过这个子任务的所有测试点才能得到这个子任务的分数。

• 子任务$1$（$30$分）：$n \leq 10$，$m \leq 20$；
• 子任务$2$（$30$分）：$n \leq 1000$，$m \leq 5000$；
• 子任务$3$（$40$分）：无特殊限制。

对于所有数据，$1 \leq n \leq 5 \times 10^{5}$，$1 \leq m \leq 10^{6}$，$1 \leq u,v \leq n$。

样例

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

1 2

19 18
17 16
7 9
3 18
16 10
14 5
9 11
11 17
10 3
6 14
5 7
2 6
8 12
19 8
4 2
15 13
1 15
13 19
18 1

16 8

见graph3.in

见graph3.out