C. 翻转DAG

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge

题目描述

给出一个 个点 条边的有向图,第 条边从 连向 ,边权为

你可以选择一些边,将其方向翻转(从 ,改为从 ),使得整张图变成一张有向无环图(DAG)。

你需要让所有翻转的边的边权最大值最小,请问这个最小值是多少,并给出具体方案。

J-04-D

输入格式

第一行两个正整数

之后 行,每行给出 个正整数 ,保证原图中存在至少一个环。

输出格式

第一行两个正整数

之后 行,每行给出 个正整数 ,保证原图中存在至少一个环。

样例

样例输入1

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

样例输出1

2 2
1 3

样例解释1

翻转第 条边。

样例输入2

5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3

样例输出2

3 3
3 4 7

样例解释2

翻转第 ​ 条边。

样例输入3,4

见下发文件。

样例输出3,4

见下发文件。

数据范围与提示

对于 的数据,​。

对于 的数据,

对于 的数据,,保证图中不存在自环,可能存在重边。