#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

enum Type{
	base_human,
	base_cat,
	base_can_area,
};

struct Info{
	Info(int arg_room_id,int arg_sum_cost){
		room_id = arg_room_id;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{
		return sum_cost > arg.sum_cost;
	}
	int room_id,sum_cost;
};

int goal;
int num_room,num_door;
int min_dist[3][NUM];
int height[NUM],boss[NUM];
vector<int> human_G[NUM],cat_G[NUM];

int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_same_group(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	//既に同じグループなら何もしない
	if(boss_x == boss_y)return;

	//高さが高い方に吸収する
	if(height[x] > height[y]){

		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void init(){
	for(int i = 0; i <= num_room; i++){ //★0が「夏への扉」の先★
		boss[i] = i;
		height[i] = 0;
	}
}

void func(){

	for(int i = 0; i <= num_room; i++){
		human_G[i].clear();
		cat_G[i].clear();
	}

	scanf("%d %d",&num_room,&num_door);

	init();

	int start_human,start_cat;
	scanf("%d %d",&start_human,&start_cat);

	int from,to;
	char buf[2];

	for(int loop = 0; loop < num_door; loop++){
		scanf("%d %d %s",&from,&to,buf);

		if(buf[0] == 'N'){ //人間用

			human_G[from].push_back(to);
			human_G[to].push_back(from);

		}else{ //猫用

			unite(from,to);

			cat_G[from].push_back(to);
			cat_G[to].push_back(from);
		}
	}

	//最初から自力ゴール可能な領域にいる場合
	if(is_same_group(goal,start_cat)){
		printf("0\n");
		return;
	}

	/*
	 * 人間がある部屋に移動する際の最小コストは猫の動きに無関係
	 */
	for(int i = 0; i <= num_room; i++)min_dist[base_human][i] = BIG_NUM;

	priority_queue<Info> Q;
	min_dist[base_human][start_human] = 0;
	Q.push(Info(start_human,0));

	int next_room,next_cost;

	//人間がある部屋に移動する最短コストを求める(通過できないので、猫用のエッジは無視)
	while(!Q.empty()){

		if(Q.top().sum_cost > min_dist[base_human][Q.top().room_id]){

			Q.pop();

		}else{

			next_cost = Q.top().sum_cost+1;

			for(int i = 0; i < human_G[Q.top().room_id].size(); i++){

				next_room = human_G[Q.top().room_id][i];

				if(min_dist[base_human][next_room] > next_cost){
					min_dist[base_human][next_room] = next_cost;
					Q.push(Info(next_room,next_cost));
				}
			}
			Q.pop();
		}
	}

	//[猫の初期稼働範囲]への、人間が到達する最短コストを逆算で求める
	for(int i = 0; i <= num_room; i++)min_dist[base_cat][i] = BIG_NUM;

	min_dist[base_cat][start_cat] = 0;
	Q.push(Info(start_cat,0));

	while(!Q.empty()){

		if(Q.top().sum_cost > min_dist[base_cat][Q.top().room_id]){

			Q.pop();

		}else{

			if(Q.top().sum_cost == 0){ //★★start地点から移動可能な範囲のみ、猫扉で移動(猫が可能な限り動いた方が最適)★★

				//猫用エッジ
				for(int i = 0; i < cat_G[Q.top().room_id].size(); i++){
					next_room = cat_G[Q.top().room_id][i];

					if(is_same_group(start_cat,next_room)){ //猫がstart地点から自力で辿り着ける部屋

						next_cost = Q.top().sum_cost;

					}else{

						next_cost = Q.top().sum_cost+1;
					}

					if(min_dist[base_cat][next_room] > next_cost){
						min_dist[base_cat][next_room] = next_cost;
						Q.push(Info(next_room,next_cost));
					}
				}
			}
			//人間用エッジ
			for(int i = 0; i < human_G[Q.top().room_id].size(); i++){

				next_room = human_G[Q.top().room_id][i];

				if(is_same_group(start_cat,next_room)){ //猫がstart地点から自力で辿り着ける部屋

					next_cost = Q.top().sum_cost;

				}else{

					next_cost = Q.top().sum_cost+1;
				}

				if(min_dist[base_cat][next_room] > next_cost){
					min_dist[base_cat][next_room] = next_cost;
					Q.push(Info(next_room,next_cost));
				}
			}

			Q.pop();
		}
	}

	//[猫が自力でゴールできる領域]への最短コストを求める
	for(int i = 0; i <= num_room; i++)min_dist[base_can_area][i] = BIG_NUM;

	min_dist[base_can_area][goal] = 0;
	Q.push(Info(goal,0));

	while(!Q.empty()){
		if(Q.top().sum_cost > min_dist[base_can_area][Q.top().room_id]){

			Q.pop();

		}else{

			if(Q.top().sum_cost == 0){ //★★猫が自力でゴール可能な範囲のみ、猫扉で移動(猫が可能な限り動いた方が最適)★★

				//猫用エッジ
				for(int i = 0; i < cat_G[Q.top().room_id].size(); i++){
					next_room = cat_G[Q.top().room_id][i];

					if(is_same_group(goal,next_room)){ //猫が自力でゴール可の部屋

						next_cost = Q.top().sum_cost;

					}else{

						next_cost = Q.top().sum_cost+1;
					}

					if(min_dist[base_can_area][next_room] > next_cost){
						min_dist[base_can_area][next_room] = next_cost;
						Q.push(Info(next_room,next_cost));
					}
				}
			}

			//人間用エッジ
			for(int i = 0; i < human_G[Q.top().room_id].size(); i++){

				next_room = human_G[Q.top().room_id][i];

				if(is_same_group(goal,next_room)){ //猫が自力でゴール可の部屋

					next_cost = Q.top().sum_cost;

				}else{

					next_cost = Q.top().sum_cost+1;
				}

				if(min_dist[base_can_area][next_room] > next_cost){
					min_dist[base_can_area][next_room] = next_cost;
					Q.push(Info(next_room,next_cost));
				}
			}
			Q.pop();
		}
	}

	int ans = BIG_NUM;
	for(int i = 0; i <= num_room; i++){
		if(min_dist[base_human][i] == BIG_NUM || min_dist[base_cat][i] == BIG_NUM || min_dist[base_can_area][i] == BIG_NUM)continue;
		ans = min(ans,min_dist[base_human][i]+min_dist[base_cat][i]+min_dist[base_can_area][i]);
	}

	printf("%d\n",ans);
}

int main(){

	int num_case;

	scanf("%d",&num_case);

	goal = 0;

	for(int i = 0; i < num_case; i++){
		func();
	}

	return 0;
}



Measured memory_bytes: 15036