← 返回题目列表

Codeforces · 240/E

E. 道路维修

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

一个名为 Berland 的国家有 n 个城市。它们用 1 到 n 的整数编号。指数为 1 的城市是该国的首都。一些城市之间建有单向道路。然而,并非所有人都状况良好。对于每条道路,我们都知道它是否需要修复。如果道路需要维修,则禁止使用。不过,贝尔兰政府可以修复这条道路,使其可以使用。

现在贝兰德正受到与邻国的战争的威胁。于是京城官员决定向各城派出一支军队。这些小队只能沿着现有的道路移动,因为没有时间或金钱来修建新道路。然而,有些道路可能需要修复才能到达某些城市。

当然,这个国家需要大量的资源来击败敌人,所以你要小心你要投入的力量。这就是为什么贝尔兰政府希望修复最少数量的道路,足以让军队沿着良好或已修复的道路从首都到达任何城市。你的任务是帮助贝尔兰政府并找出哪些道路需要修复。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — Berland 的城市数量和道路数量。

接下来 m 行包含三个空格分隔的整数 ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci ≤ 1),描述从城市 ai 到城市 bi 的道路。如果 ci 等于 0,则给定的道路状况良好。如果ci等于1,则需要修复。

保证每个方向的城市之间不超过一条道路。

输出

如果所有道路都修好后,仍然无法从首都到达某个城市,则打印 - 1。否则,在第一行打印需要修缮的最少道路数,在第二行打印这些道路的编号,以单个空格分隔。

道路按照输入中给出的顺序从 1 开始编号。

如果有多组,其中包括需要修复的最少数量的道路,以便可以从首都前往任何城市,请打印其中的任何一组。

如果可以沿着已经状况良好的道路行驶到达任何城市,则在唯一的输出行中打印 0。

示例

输入 #1

3 2
1 3 0
3 2 1

输出 #1

1
2

输入 #2

4 4
2 3 0
3 4 0
4 1 0
4 2 1

输出 #2

-1

输入 #3

4 3
1 2 0
1 3 0
1 4 0

输出 #3

0