Problem:


Problem I: 夏への扉

なつめは大のねこ好きである。なつめの家ではずっとねこを飼っておらず、ねこ好きななつめはいつも野良ねこと遊んでいた。しかし、今回なつめは決心し、自分の家でねこを一匹飼うことにした。なつめはねこを家に迎え、レノンと名付けてかわいがり始めた。

なつめの家はたくさんの部屋と、それらをつなぐたくさんの扉からなっており、扉は次の2種類がある。

    人間用の普通の扉
    なつめは開けることができるが、レノンが自分で開けることはできない。なつめとレノンの両方が通ることができる。一度開ければ、その後は開いたままにしておける。
    ねこ用の小さな扉
    レノンが自分であけて自由に通ることができる。ただし小さいために、なつめが通ることはできない。

レノンは夏が大好きである。だから、冬になり家の外がまっしろな雪で覆われてしまう頃になると、彼の機嫌はとても悪くなってしまった。しかし、彼は家にたくさんあるドアのうち、あるひとつの扉が「夏」へとつながっていると信じているようだった。なつめはその扉を「夏への扉」と呼んでいる。そして、寒くて不機嫌になってくると、レノンはきまってその扉の向こうへ行きたがるのである。

冬のある日、レノンがまた「夏への扉」の奥へ行こうと思い立った。しかし、レノンがひとりで扉を開けて、夏への扉の奥へ行けるとは限らない。その時はもちろん、なつめはレノンの手伝いをしなければならない。つまり、なつめしか開けることの出来ない扉をいくつか開いて、レノンが「夏への扉」の向こう側へ行けるようにしてあげるのだ。

最初、家の中の全ての扉は閉まっている。家の部屋の接続関係、なつめおよびレノンの初期位置が与えられる。なつめとレノンが最適な戦略をとった時、レノンが「夏への扉」の先へいくためになつめが開けなければならない扉の最小数を計算しなさい。

以下の図は、サンプル入力の例を図示したものである。

図: サンプル入力の初期状態

Input

入力の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を満たす。

Output

なつめが開けなければならない扉の最小数を、1行で出力せよ。

Notes on Submission

上記形式で複数のデータセットが与えられます。入力データの 1 行目にデータセットの数が与えられます。各データセットに対する出力を上記形式で順番に出力するプログラムを作成して下さい。

Sample Input

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

Output for the Sample Input

1
3



Sample input:
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


Sample output:
1
3

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

INF = 10 ** 9
L = input()

for loop in range(L):
    n, m = map(int, raw_input().split())
    S, T = map(int, raw_input().split())
    E = [[] for i in range(n + 1)]
    for i in range(m):
        u, v, tp = raw_input().split()
        u = int(u)
        v = int(v)
        E[u].append((v, tp))
        E[v].append((u, tp))
    C1 = [INF] * (n + 1)
    que = deque()
    que.append((S, 0))
    while len(que) > 0:
        p = que.popleft()
        if C1[p[0]] <= p[1]:
            continue
        C1[p[0]] = p[1]
        for e in E[p[0]]:
            if e[1] == 'N':
                que.append((e[0], p[1] + 1))
    
    C2 = [INF] * (n + 1)
    que = deque()
    que.append((T, 0))
    while len(que) > 0:
        p = que.popleft()
        if C2[p[0]] <= p[1]:
            continue
        C2[p[0]] = p[1]
        for e in E[p[0]]:
            if e[1] == 'L':
                que.append((e[0], p[1]))
    if C2[0] == 0:
        print 0
        continue
    que = deque()
    for i in range(n + 1):
        if C2[i] == 0:
            que.append((i, 0))
    C2 = [INF] * (n + 1)
    while len(que) > 0:
        p = que.popleft()
        if C2[p[0]] <= p[1]:
            continue
        C2[p[0]] = p[1]
        for e in E[p[0]]:
            if e[1] == 'N':
                que.append((e[0], p[1] + 1))
    
    C3 = [INF] * (n + 1)
    que = deque()
    que.append((0, 0))
    while len(que) > 0:
        p = que.popleft()
        if C3[p[0]] <= p[1]:
            continue
        C3[p[0]] = p[1]
        for e in E[p[0]]:
            if e[1] == 'L':
                que.append((e[0], p[1]))
    que = deque()
    for i in range(n + 1):
        if C3[i] == 0:
            que.append((i, 0))
    C3 = [INF] * (n + 1)
    while len(que) > 0:
        p = que.popleft()
        if C3[p[0]] <= p[1]:
            continue
        C3[p[0]] = p[1]
        for e in E[p[0]]:
            if e[1] == 'N':
                que.append((e[0], p[1] + 1))
    ans = 10 ** 9
    for i in range(1, n + 1):
        ans = min(ans, C1[i] + C2[i] + C3[i])
    print ans