P17772 道路检修

小 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`。

### 样例 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$ 条； - 任意两个地点之间至多有一条道路。 本题采用子任务捆绑测试。只有通过一个测试包中的全部测试点，才能获得该测试包的分数。各测试包的详细数据范围见下表。 | 子任务编号 | $m$ | 需反转的道路数 | 特殊性质 | 分值 | | :---: | :---: | :---: | :---: | :---: | | $1$ | $\le 12$ | $\le 30$ | 无 | $15$ | | $2$ | $\le 5000$ | $\le 30$ | A | $15$ | | $3$ | $\le 5000$ | $\le 3$ | 无 | $20$ | | $4$ | $\le 5000$ | $\le 15$ | 无 | $20$ | | $5$ | $\le 5000$ | $\le 30$ | 无 | $30$ | 需反转的道路数指满足 $b_i = 1$ 的道路数量。 特殊性质 A：忽略道路方向后，原图不包含环。