CF780F Axel and Marston in Bitland

一对朋友，Axel 和 Marston，正在 Bitland 全国各地旅行。Bitland 有 $n$ 个城镇，部分城镇之间由单向道路连接。每条道路要么是步行道路，要么是自行车道路。任意两个城镇之间可以有多条道路，甚至一个城镇可以通向自身。但不会存在两条起点、终点和类型都相同的道路。 现在两位朋友在城镇 $1$ ，他们计划旅行路线。Axel 喜欢步行，Marston 更喜欢骑自行车。为了让路线对两人都足够多样和有趣，他们决定按照如下流程选择路段类型： - 路线从步行道路（P）开始。 - 假设路线开头写成了一个由字母 P（步行道路）和 B（自行车道路）组成的字符串 $s$，那么再追加字符串 $oppo(s)$ 到 $s$ 后面，这里 $oppo(s)$ 表示将 $s$ 中每个字符都变为相反类型（P 变 B，B 变 P）。 前几步的路线类型字符串依次为：P，PB，PBBP，PBBPBPPB，PBBPBPPBBPPBPBBP，依此类推。 之后，两人就按照上述规则，从城镇 $1$ 出发，依次按照路线类型选择道路。如果无法选择下一条要求类型的道路，旅行就终止并直接回家。 请你帮忙找出两位朋友按照上述规则最多能走多长的路。如果能构造出一条长度大于 $10^{18}$ 的路线，请输出 $-1$。

第一行包含两个整数 $n$ 和 $m$（$1\leq n\leq 500$，$0\leq m\leq 2n^2$）—— Bitland 的城镇数和道路数。 接下来 $m$ 行，每行描述一条道路。第 $i$ 行包含三个整数 $v_i$、$u_i$ 和 $t_i$（$1\leq v_i, u_i \leq n$，$0\leq t_i \leq 1$），$v_i$ 和 $u_i$ 表示该道路的起点和终点城镇编号，$t_i$ 表示道路的类型（0 代表步行道，1 代表自行车道）。保证对于所有 $1\leq i, j \leq m$ 且 $i\neq j$，都有 $v_i\neq v_j$，或 $u_i\neq u_j$，或 $t_i\neq t_j$。

如果可以找到长度严格大于 $10^{18}$ 的路线，输出 $-1$。否则，输出满足条件的最大路径长度。

在第一个样例中，可以走 3 条路：先从城镇 1 到城镇 2，接下来两次从城镇 2 自己绕回自己。 在第二个样例中，可以无限制延长路线：先走第一条路，然后根据所需类型选择第二条或第三条路。 由 ChatGPT 5 翻译