几个朋友 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 来获得任意长的路线。