GraphRGB

問題

$N$頂点の$M$辺の無向グラフがあります。辺$i$は頂点$u_i, v_i$を結びます。

R,G,Bから成る文字列$S$が与えられます。

$i$番目の頂点には文字$S_i$が書いてあります。

頂点に書いてある文字が、R->G->Bの順でたどれる長さ2の経路は何個ありますか？

制約

• $3 \leqq N \leqq 2 \times 10^{5}$
• $1 \leqq M \leqq \min(2\times 10^5, N(N-1)/2)$
• $1 \leqq u_i < v_i \leqq N$
• $i \neq j \to (u_i, v_i) \neq (u_j, v_j)$
• $|S| = N$
• $S_i$はR,G,Bのいずれか

入力

N M
u_1 v_1
...
u_m v_m
S

入力例１

5 4
1 2
2 3
3 4
4 5
RGBGR

出力例１

2

$1 \to 2 \to 3$と$5 \to 4 \to 3$の２つの経路があります。

入力例２

5 4
4 5
1 5
3 4
2 3
GBGRB

出力例２

1