#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define pb         push_back
const int N = 100005;
const int inf = ( 1 << 21);


class Edge{
public:
  int next,c;
};

class state{
public:
  int now,c;
  bool operator<(const state & a)const{
    return c > a.c;
  }
};

void dijkstra(vector<int>&ini,int n,vector<Edge> *edge,int *cost){
  rep(i,n)cost[i]=inf;
  
  priority_queue<state>  Q;
  rep(i,ini.size()){
    Q.push((state){ini[i],0});
  }
  
  while(!Q.empty()){
    state now = Q.top();Q.pop();
    if (cost[now.now] != inf)continue;
    cost[now.now]=now.c;
    rep(i,edge[now.now].size()){
      int next=edge[now.now][i].next,nec=now.c+edge[now.now][i].c;
      Q.push((state){next,nec});
    }
  }
}

vector<Edge> Ledge[N],Nedge[N];
int Lcost[N],Scost[N],Ncost[N];
int LBFS[N],SBFS[N];

template<class T> void op(T &in,int n){rep(i,n)cout<<in[i]<<' ';cout << endl;}

int solve(int n,int L,int S,int N){
  vector<int> ini;
  ini.push_back(L);
  dijkstra(ini,n,Ledge,LBFS);
  //  op(LBFS,n);
  if (LBFS[S] != inf)return 0;//natune is not needed
  ini.clear();

  

  ini.push_back(S);
  dijkstra(ini,n,Ledge,SBFS);
  ini.clear();

  //  op(SBFS,n);


  vector<int> Lini,Nini,Sini;
  Nini.push_back(N);
  rep(i,n){
    if (LBFS[i] != inf)Lini.push_back(i);
    if (SBFS[i] != inf)Sini.push_back(i);
  }

  dijkstra(Lini,n,Nedge,Lcost);
  dijkstra(Sini,n,Nedge,Scost);
  dijkstra(Nini,n,Nedge,Ncost);

  
  int ans = inf;
  rep(i,n){
    //if (LBFS[i] == inf && SBFS[i] == inf)
      ans=min(ans,Ncost[i]+Scost[i]+Lcost[i]);
  }
  return ans;
}


int main(){
  int te;
  cin>>te;
  while(te--){
    int n,m;
    cin>>n >>m;
    n++;
    rep(i,n)Nedge[i].clear(),Ledge[i].clear();
    int S = 0,L,N;
    cin>>N>>L;

    rep(i,m){
      int f,t;
      char k;
      cin>>f>>t>>k;
      if (k == 'L'){
	Ledge[f].pb((Edge){t,1});
	Ledge[t].pb((Edge){f,1});
      }else if (k == 'N'){
	Nedge[f].pb((Edge){t,1});
	Nedge[t].pb((Edge){f,1});
      }
    }
    cout << solve(n,L,S,N) << endl;
  }
}