← 返回题目列表

Codeforces · 780/F

F. 阿克塞尔和马斯顿在比特兰

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

几个朋友 Axel 和 Marston 正在穿越 Bitland 国家。比特大陆有 n 个城镇,其中一些城镇通过单向道路连接。 Bitland 的每条道路要么是步行道,要么是自行车道。任意一对城镇之间可以有多条道路,甚至可以是从城镇到城镇本身的道路。然而,没有哪条道路同时共享起始城镇和目的地城镇及其类型。

小伙伴们现在位于城镇1,正在规划出行路线。阿克塞尔喜欢步行,而马斯顿则喜欢骑自行车。为了让双方朋友能够选择一条多样化且同样有趣的路线,双方约定在出行过程中选择道路类型的程序如下:

- 路线以步行路线开始。
- 假设路线的开头写在字母 P(步行道)和 B(自行车道)组成的字符串 s 中。然后,将字符串 $$s$$ 附加到 s 后面,其中 $$s$$ 代表字符串 s 的每个字符改为相反(即所有步行道改为自行车道,反之亦然)。

在前几步中,路线将如下所示:P、PB、PBBP、PBBPBPPB、PBBPBPPBBPPBPBBP 等。

之后,朋友们开始从城镇 1 出发,通过 Bitlandian 道路行驶,每次根据路线类型的下一个字符选择下一条道路。如果无法选择下一条路,朋友们就会终止行程,飞回家。

帮助小伙伴们按照上述道路类型选择程序,找到比特大陆道路上可以行驶的最长路线。如果存在这样一条路线,其中的道路数量超过 1018 条,则打印 -1。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 500, 0 ≤ m ≤ 2n2) – 分别是 Bitland 中城镇和道路的数量。

接下来的 m 行描述道路。其中第 i 行包含三个整数 vi、ui 和 ti(1 ≤ vi、ui ≤ n、0 ≤ ti ≤ 1),其中 vi 和 ui 表示第 i 条道路的起点和目的地城镇索引,ti 描述第 i 条道路的类型(0 为步行道,1 为自行车道)。保证对于每对不同的索引 i、j,使得 1 ≤ i、j ≤ m,vi ≠ vj 或 ui ≠ uj 或 ti ≠ tj 成立。

输出

如果可以找到长度严格大于1018的路线,则打印-1。否则,打印合适路径的最大长度。

示例

输入 #1

2 2
1 2 0
2 2 1

输出 #1

3

输入 #2

2 3
1 2 0
2 2 1
2 2 0

输出 #2

-1

注意

在第一个样本中,我们可以通过沿着道路 1 从城镇 1 行驶到城镇 2,然后沿着道路 2 两次从城镇 2 行驶到城镇,获得长度为 3 的路线。

在第二个示例中,我们可以通过先行驶道路 1,然后根据所需类型选择道路 2 或 3 来获得任意长的路线。