The Door into Summer

Natsume loves big cats. I haven't kept cats at Natsume's house for a long time, and Natsume, who loves cats, was always playing with stray cats. However, this time Natsume decided to keep a cat at her own house. Natsume welcomed the cat to her house and named her Lennon and began to pet her.

Natsume's house consists of many rooms and many doors that connect them, and there are two types of doors.

Ordinary door for humans Jujube can be opened, but Lennon cannot open it himself. Both jujube and Lennon can pass through. Once opened, it can be left open thereafter. Small door for cats Lennon can open himself and pass freely. However, because it is small, jujube cannot pass through.

Lennon loves summer. So when it was winter and the outside of the house was covered with pure snow, he was in a bad mood. However, he seemed to believe that one of the many doors in the house led to "summer." Natsume calls the door "the door to summer." And when it gets cold and moody, Lennon wants to go beyond the door.

One winter day, Lennon decided to go deeper into the "door to summer." However, it is not always possible for Lennon to open the door alone and go to the back of the door to summer. At that time, of course, Natsume must help Lennon. In other words, open some doors that can only be opened by jujube, allowing Lennon to go beyond the "door to summer."

At first, all the doors in the house are closed. Given the room connectivity of the house, the initial position of jujube and Lennon. When Natsume and Lennon take the best strategy, calculate the minimum number of doors that Lennon must open to go beyond the "doors to summer".

The figure below illustrates an example of sample input.

1st sample input 2nd sample input Figure: Initial state of sample input

Notes on Submission

Multiple datasets are given in the above format. The first line of input data gives the number of datasets. Create a program that outputs the output for each data set in order in the above format.

Input

On the first line of input, the number of rooms n and the number of doors m are given, separated by a single space character. Each room is assigned a number from 0 to n, where 0 represents the "door to summer". The second line is given the number of the room where Natsume is first and the number of the room where Lennon is first, separated by a single space character. Both room numbers are greater than or equal to 1 and are never beyond the "door to summer" from the beginning. The following m lines are given one line of information for each of the m doors. Each line consists of two room IDs and a one-letter alphabet that represents the type of door, separated by a single space character. The door connects the two designated rooms, and the type is a normal door for humans when the alphabet is N, and a small door for cats when the alphabet is L. Doors do not connect rooms with the same door. The door that contains the room ID 0 is the "door to summer", and there is always only one door during entry. Satisfy 1 <= n, m <= 100000.

Output

Output the minimum number of doors that the jujube must open in one line.

Example

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

1 3

inputFormat

input.

1st sample input 2nd sample input Figure: Initial state of sample input

Notes on Submission

Multiple datasets are given in the above format. The first line of input data gives the number of datasets. Create a program that

outputFormat

outputs the output for each data set in order in the above format.

Input

On the first line of input, the number of rooms n and the number of doors m are given, separated by a single space character. Each room is assigned a number from 0 to n, where 0 represents the "door to summer". The second line is given the number of the room where Natsume is first and the number of the room where Lennon is first, separated by a single space character. Both room numbers are greater than or equal to 1 and are never beyond the "door to summer" from the beginning. The following m lines are given one line of information for each of the m doors. Each line consists of two room IDs and a one-letter alphabet that represents the type of door, separated by a single space character. The door connects the two designated rooms, and the type is a normal door for humans when the alphabet is N, and a small door for cats when the alphabet is L. Doors do not connect rooms with the same door. The door that contains the room ID 0 is the "door to summer", and there is always only one door during entry. Satisfy 1 <= n, m <= 100000.

Output

Output the minimum number of doors that the jujube must open in one line.

Example

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

1 3

样例

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

</p>