P17481 平衡路线

给定一张有 $n$ 个顶点、$m$ 条边的无向图，每条边带有符号 `'+'` 或 `'-'`。对于一条从顶点 $s$ 到顶点 $t$ 的路线，允许重复经过顶点和边。定义一条路线的权值如下：记 $n^+,n^-$ 分别为经过的 `'+'` 边数和经过的 `'-'` 边数，则该路线的权值为 $|n^+-n^-|$。 请计算从 $s$ 到 $t$ 的路线的最小权值。若不存在从 $s$ 到 $t$ 的路线，则输出 −1。

输入第一行为四个整数 $n,m,s,t$。接下来 $m$ 行，每行给出两个整数 $a,b$ 和一个字符 `'+'` 或 `'-'`，描述一条连接 $a$ 与 $b$ 的无向边及其符号。

输出一个整数，表示从 $s$ 到 $t$ 的路线的最小权值。若不存在从 $s$ 到 $t$ 的路线，则输出 $-1$。

数据满足 $2\le n\le2\times10^5$，$1\le m\le4\times10^5$，$1\le s,t\le n$ 且 $s\ne t$，$1\le a,b\le n$，可能出现重边。