题目描述

给定一张有 $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$。

5 4 1 3
1 2 +
2 3 +
2 4 +
4 5 -

0

3 2 1 2
1 2 +
2 3 -

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$，可能出现重边。