j02038. 红蓝信使 未做

某城市有 $n$ 个路口和 $m$ 条双向道路。每条道路被漆成红色($R$)或蓝色($B$)之一，走过任何一条道路都恰好花 1 分钟。信使要从 1 号路口赶往 $n$ 号路口，但按调度规定，他连续走过的两条道路颜色不许相同（出发后的第一条路颜色随意）。求最少花多少分钟到达；若无法按规定到达，输出 -1（允许重复经过路口与道路）。

第一行两个整数 $n$ $m$；接下来 $m$ 行每行两个整数 $u$ $v$ 和一个字符 $c$（$c$ 为 $R$ 或 $B$），表示 $u$ $v$ 之间有一条颜色 $c$ 的双向道路。

一行一个整数，最少分钟数或 -1。

• 30% 1$\le$$n$$\le$8，0$\le$$m$$\le$12（枚举所有路径可过）。
• 60% 1$\le$$n$$\le$2000，0$\le$$m$$\le$4000。
• 100% 1$\le$$n$$\le$$5\times 10^4$，0$\le$$m$$\le$$8\times 10^4$，$1\le u,v\le n$，$c$ 为 $R$ 或 $B$。