学生会选举即将在下周举行。本次选举有两位候选人：Alya 和 Yuki。由于某些原因，你认为这次选举一团糟，且因为你不想惹麻烦，你希望在选举结束前尽可能保持中立。

校园内有 $N$ 栋建筑和 $M$ 条连接它们的走廊。第 $i$ 条走廊连接第 $u_i$ 栋和第 $v_i$ 栋建筑。任意两栋建筑之间最多只有一条走廊相连，且不存在连接建筑自身的走廊。

每条走廊上都有其中一位候选人的竞选团队。每当有人走过一条走廊，他们就会收到一张该候选人的传单，上面印有精美的插图。

目前，你位于第 $1$ 栋建筑，正前往第 $N$ 栋建筑。你想要规划一条路径，使得你收到的两位候选人的传单数量之差尽可能小。注意，你可以多次经过同一条走廊，即使已经到达了第 $N$ 栋建筑，只要你的路径是从第 $1$ 栋建筑出发并最终在第 $N$ 栋建筑结束，你仍然可以继续行走。

请编写一个程序来计算可能的最小差值，或者判断是否无法到达第 $N$ 栋建筑。

输入格式

第一行包含两个整数 $N$ 和 $M$：校园内建筑的数量和走廊的数量（$2 \le N \le 3 \cdot 10^5$；$0 \le M \le 3 \cdot 10^5$）。

接下来的 $M$ 行，每行包含两个整数 $u_i$ 和 $v_i$ 以及一个字符 $c_i$（$1 \le u_i, v_i \le N$；$u_i \neq v_i$；对于所有 $i \neq j$，$\{u_i, v_i\} \neq \{u_j, v_j\}$）。它们表示第 $i$ 条走廊连接第 $u_i$ 栋和第 $v_i$ 栋建筑，如果 $c_i = \text{A}$，则该走廊上有 Alya 的竞选团队；如果 $c_i = \text{Y}$，则该走廊上有 Yuki 的竞选团队。

输出格式

如果无法到达第 $N$ 栋建筑，输出 $-1$。

否则，输出一个整数：你收到的两位候选人的传单数量之差的最小值。

样例

样例输入 1

4 3
1 2 Y
2 3 Y
3 4 A

样例输出 1

1

样例输入 2

4 3
1 2 Y
2 4 Y
3 4 A

样例输出 2

0

样例输入 3

2 0

样例输出 3

-1

说明

在第一个样例中，沿着路径 $1 \to 2 \to 3 \to 4$ 行走，你将收到 $2$ 张 Yuki 的传单和 $1$ 张 Alya 的传单。差值为 $1$。可以证明不存在差值为 $0$ 的路径，因此答案为 $1$。

在第二个样例中，沿着路径 $1 \to 2 \to 4 \to 3 \to 4$ 行走，你将收到 $2$ 张来自两位候选人的传单，因此答案为 $0$。

在第三个样例中，无法到达第 $2$ 栋建筑，因此输出 $-1$。