#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
#include <complex>
#include <numeric>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int MOD = 1e9+7;


typedef int Weight;
const Weight INF=99999999;
struct Edge{
    int src,dst;
    Weight weight;
    int rev;
    Edge(int f, int t, Weight c, int rev=0):src(f),dst(t),weight(c),rev(rev){}
    bool operator < (const Edge& re)const{ return weight > re.weight;}
};
typedef vector<vector<Edge> > Graph;
void add_edge(Graph &G, int s, int t, Weight cap){
    G[s].push_back(Edge(s, t, cap, G[t].size()));
}
void shortestPath(const Graph &g, int s, vector<Weight> &dist, vector<int> &prev) {
    int n = g.size();
    dist.assign(n, INF); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> Q;
    for(Q.push(Edge(-2, s, 0)); !Q.empty();){
        Edge e = Q.top(); Q.pop();
        if(prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        FOR(f,g[e.dst]) {
            if (dist[f->dst] > e.weight+f->weight){
                dist[f->dst] = e.weight+f->weight;
                Q.push(Edge(f->src, f->dst, e.weight+f->weight));
            }
        }
    }
}
void bfs(const Graph &g, int s, vector<Weight> &dist, vector<int> &prev) {
    int n = g.size();
    dist.assign(n, INF); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> Q;
    for(Q.push(Edge(-2, s, 0)); !Q.empty();){
        Edge e = Q.top(); Q.pop();
        if(prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        FOR(f,g[e.dst]) {
            if(e.weight != 0 && f->weight == 0) continue;
            if (dist[f->dst] > e.weight+f->weight){
                dist[f->dst] = e.weight+f->weight;
                Q.push(Edge(f->src, f->dst, e.weight+f->weight));
            }
        }
    }
}


int main(void){
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        int natsume, lennon;
        cin >> natsume >> lennon;
        natsume--; lennon--;
        Graph g(n), lg(n), sg(n);
        int summer, tosummer = 0;
        vector<pii> cat;
        REP(i, m){
            int x, y; char c;
            cin >> x >> y >> c;
            x--; y--;

            if(min(x, y) == -1){
                summer = max(x, y);
                if(c == 'N') tosummer = 1; 
                else tosummer = 0;
                continue;
            }

            if(c == 'N'){
                add_edge(g, x ,y, 1);
                add_edge(g, y, x, 1);
                add_edge(lg, x ,y, 1);
                add_edge(lg, y, x, 1);
                add_edge(sg, x ,y, 1);
                add_edge(sg, y, x, 1);
            }else{
                cat.push_back(pii(x, y));
                add_edge(lg, x ,y, 0);
                add_edge(lg, y ,x, 0);
            }
        }
        if(!tosummer){
            FOR(e, cat){
                add_edge(sg, (*e).first, (*e).second, 0); 
                add_edge(sg, (*e).second, (*e).first, 0);
            }
        }
        vi dist_g, dist_lg, dist_sg, prev;
        shortestPath(g, natsume, dist_g, prev);
        prev.clear();
        bfs(lg, lennon, dist_lg, prev);
        prev.clear();
        bfs(sg, summer, dist_sg, prev);
        int ans = INF;
        if(!tosummer && dist_sg[lennon] == 0){
            cout << 0 << endl;
            continue;
        }
        REP(i, n){
            //cout << dist_g[i] << ":" << dist_lg[i] << ":" << dist_sg[i] << endl;
            ans = min(ans, dist_g[i] + dist_lg[i] + dist_sg[i] + tosummer);
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 25492