题目描述

小 Y 受邀来到一座交通试验场，驾驶专用检修车调整场内单向道路的通行方向。

试验场内共有 $n$ 个地点（编号为 $1 \sim n$）和 $m$ 条单向道路。每条道路连接两个不同的地点，且任意两个地点之间至多存在一条道路。图不保证连通。

检修车初始位于地点 $s$。在每一步移动中，小 Y 可以选择一条以当前所在地点为起点的道路，沿其当前允许通行的方向行驶至道路的另一端；当检修车通过该道路后，这条道路的通行方向会立即反转，而其余道路的方向保持不变。地点和道路均允许重复经过。

第 $i$ 条道路的初始方向为 $u_i \to v_i$，其目标方向由参数 $b_i \in \{0, 1\}$ 给定：

• 若 $b_i = 0$，表示该道路最终需要与初始方向相同（即 $u_i \to v_i$）；
• 若 $b_i = 1$，表示该道路最终需要与初始方向相反（即 $v_i \to u_i$）。

小 Y 可以在任意地点结束行程（不必回到起点 $s$，也可以一步都不走）。请帮小 Y 计算，要使所有道路同时达到目标方向，检修车最少需要行驶多少步？若无论如何行驶都无法达成目标，则输出 -1。

输入格式

从标准输入读入数据。

第一行包含三个整数 $n, m, s$，分别表示地点数量、道路数量以及检修车的初始位置。

接下来 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i, b_i$，描述第 $i$ 条道路的初始方向 $u_i \to v_i$ 及目标要求 $b_i$。

输出格式

输出到标准输出。

输出一行一个整数，表示达成目标所需的最少步数；若无法完成，输出 -1。

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

5

2 1 1
2 1 1

-1

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

0

提示

样例 1 解释

小 Y 可以按 $1 \to 2 \to 3 \to 4 \to 2 \to 1$ 的路线行驶，共走 $5$ 步。其中连接地点 $1, 2$ 的道路被经过两次，方向恢复为初始状态；其余三条道路各被经过一次，方向均发生反转，所有道路恰好达到目标方向。可以证明不存在步数更少的方案。

样例 2 解释

检修车初始位于地点 $1$，而唯一一条道路的初始方向为 $2 \to 1$，检修车无法移动，故无解。

样例 3 解释

初始时所有道路均已处于目标方向，无需移动。

样例 4

见题目附件中的 routes/routes4.in 与 routes/routes4.ans。该样例满足子任务 $4$ 的约束条件。

样例 5

见题目附件中的 routes/routes5.in 与 routes/routes5.ans。该样例满足子任务 $4$ 的约束条件。

样例 6

见题目附件中的 routes/routes6.in 与 routes/routes6.ans。该样例满足子任务 $5$ 的约束条件。

子任务

对于全部数据，保证：

• $1 \le n \le 1500$，$0 \le m \le \min\left(5000, \dfrac{n(n-1)}{2}\right)$；
• $1 \le s, u_i, v_i \le n$，且 $u_i \ne v_i$；
• $b_i \in \{0, 1\}$，且满足 $b_i = 1$ 的道路不超过 $30$ 条；
• 任意两个地点之间至多有一条道路。

本题采用子任务捆绑测试。只有通过一个测试包中的全部测试点，才能获得该测试包的分数。各测试包的详细数据范围见下表。

需反转的道路数指满足 $b_i = 1$ 的道路数量。

特殊性质 A：忽略道路方向后，原图不包含环。