AdditionalFile4895.zip

#4895. 「POI2014 R2」拉力赛 Rally

标签: 传统 | 时间限制: 7000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXI Olimpiada Informatyczna — II etap Rajd

P3573 [POI 2014] RAJ-Rally

题目描述

给定一个 $n$ 个点 $m$ 条边的有向无环图，每条边长度都是 $1$。

请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。

输入格式

第一行包含两个正整数 $n$，$m$（$2\le n\le5\times10^5$，$1\le m\le10^6$），表示点数、边数。

接下来 $m$ 行每行包含两个正整数 $a_i,b_i$（$1\le a_i,b_i\le n,a_i\ne b_i$），表示 $a_i$ 到 $b_i$ 有一条边。

输出格式

包含一行两个整数 $x$，$y$，用一个空格隔开，$x$ 为要删去的点，$y$ 为删除 $x$ 后图中的最长路径的长度，如果有多组解请输出任意一组。

输入输出样例 #1

输入 #1

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

输出 #1

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}$。