問題


頂点の辺の無向グラフがあります。辺は頂点を結びます。

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

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

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

制約


  • はR,G,Bのいずれか

入力


N M
u_1 v_1
...
u_m v_m
S

入力例1


5 4
1 2
2 3
3 4
4 5
RGBGR

出力例1


2

の2つの経路があります。

入力例2


5 4
4 5
1 5
3 4
2 3
GBGRB

出力例2


1

提出


Go (1.14)