図: サンプル入力の初期状態
なつめは大のねこ好きである。なつめの家ではずっとねこを飼っておらず、ねこ好きななつめはいつも野良ねこと遊んでいた。しかし、今回なつめは決心し、自分の家でねこを一匹飼うことにした。なつめはねこを家に迎え、レノンと名付けてかわいがり始めた。
なつめの家はたくさんの部屋と、それらをつなぐたくさんの扉からなっており、扉は次の2種類がある。
レノンは夏が大好きである。だから、冬になり家の外がまっしろな雪で覆われてしまう頃になると、彼の機嫌はとても悪くなってしまった。しかし、彼は家にたくさんあるドアのうち、あるひとつの扉が「夏」へとつながっていると信じているようだった。なつめはその扉を「夏への扉」と呼んでいる。そして、寒くて不機嫌になってくると、レノンはきまってその扉の向こうへ行きたがるのである。
冬のある日、レノンがまた「夏への扉」の奥へ行こうと思い立った。しかし、レノンがひとりで扉を開けて、夏への扉の奥へ行けるとは限らない。その時はもちろん、なつめはレノンの手伝いをしなければならない。つまり、なつめしか開けることの出来ない扉をいくつか開いて、レノンが「夏への扉」の向こう側へ行けるようにしてあげるのだ。
最初、家の中の全ての扉は閉まっている。家の部屋の接続関係、なつめおよびレノンの初期位置が与えられる。なつめとレノンが最適な戦略をとった時、レノンが「夏への扉」の先へいくためになつめが開けなければならない扉の最小数を計算しなさい。
以下の図は、サンプル入力の例を図示したものである。
入力の1行目には、部屋の数 n と扉の数 m が1つの空白文字で区切って与えられる。部屋にはそれぞれ 0 から n の番号が割り振られており、0は「夏への扉」の先をあらわす。2行目はなつめが最初にいる部屋の番号とレノンが最初にいる部屋の番号が、1つの空白文字で区切って与えられる。どちらの部屋番号も1以上であり、最初から「夏への扉」の先にいることはない。続く m 行には、m 枚の扉の情報がそれぞれ1行ずつ与えられる。各行はふたつの部屋IDと扉の種類を表す1文字のアルファベットからなり、1つの空白文字で区切られている。扉は指定されたふたつの部屋を繋いでおり、種類はアルファベットが N のとき人間用の普通の扉、L のときねこ用の小さな扉である。扉が同じ部屋同士を繋ぐことはない。部屋IDが0のものを含む扉が「夏への扉」であり、これは入力中に必ずただ1つ存在する。1 <= n, m <= 100000を満たす。
なつめが開けなければならない扉の最小数を、1行で出力せよ。
上記形式で複数のデータセットが与えられます。入力データの 1 行目にデータセットの数が与えられます。各データセットに対する出力を上記形式で順番に出力するプログラムを作成して下さい。
2 4 6 1 2 1 2 N 2 3 N 3 4 N 4 1 N 1 4 L 4 0 L 4 6 1 2 1 2 N 2 3 N 3 4 N 4 1 N 1 4 L 4 0 N
1 3