← 返回题目列表

Codeforces · 1100/E

E. 安德鲁和出租车

中文机器翻译题面 查看原题

与其他交通工具相比,安德鲁更喜欢出租车,但最近大多数出租车司机的行为不当。为了赚更多的钱,出租车司机开始兜圈子。安德鲁市的道路是单向的,人们没有必要能够从一个地方前往另一个地方,但这与阴险的出租车司机相比就显得相形见绌了。

市长决定改变某些道路的走向,这样出租车司机就无法无休止地增加出行成本。更正式地说,如果出租车司机位于某个十字路口,如果他执行非零行程,他们将无法再次到达该十字路口。

需要交通管制员来改变道路的行驶方向。对于每条道路,都知道需要多少交通管制员才能将道路方向更改为相反的方向。允许逐条改变道路方向,即每个交通管制员可以参与两条或更多条道路的倒车。

您需要计算执行任务所需雇用的最少交通管制员数量以及需要倒车的道路列表。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 100\,000$$$, $$$1 \leq m \leq 100\,000$$$)——分别是城市中的十字路口数量和道路数量。

以下 $$$m$$$ 行均包含三个整数 $$$u_{i}$$$、$$$v_{i}$$$ 和 $$$c_{i}$$$ ($$$1 \leq u_{i}, v_{i} \leq n$$$, $$$1 \leq c_{i} \leq 10^9$$$, $$$u_{i} \ne v_{i}$$$) — 道路起点的十字路口、道路终点的十字路口以及倒车所需的交通管制员数量。

输出

在第一行中输出两个整数,即完成任务所需的最少交通控制器数量和应反转的道路数量 $$$k$$$。 $$$k$$$ 不应最小化。

在下一行中输出 $$$k$$$ 个由空格分隔的整数 — 道路数量,其方向应相反。道路按照输入中写入的顺序从 $$$1$$$ 开始编号。如果有很多解决方案,请打印其中任何一个。

示例

输入 #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

输入 #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

注意

第一个示例中有两个简单的循环:$$$1 \rightarrow 5 \rightarrow 2 \rightarrow 1$$$ 和 $$$2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$$$。一名交通管制员只能逆转道路 $$$2 \rightarrow 1$$$ 并且他无法自行破坏第二个循环。两个交通管制员可以逆转道路 $$$2 \rightarrow 1$$$ 和 $$$2 \rightarrow 3$$$ 满足条件。

在第二个示例中,一名交通管制员无法破坏循环 $$$ 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 $$$。例如,在三个控制器的帮助下,我们可以反转道路 $$$1 \rightarrow 3$$$ 、$$$ 2 \rightarrow 4$$$、$$$1 \rightarrow 5$$$。