929 . The Door of Summer
Description
Natsume loved cat so much, and she got one home and named the cat Lennon. In Natsume's home, which consisted of rooms and doors between two rooms. There were two kind of doors, one kind for human -- both Natsume and Lennon can passthru but only Natsume can open it -- and one kind for cats -- only Lennon can passthrough.
Lennon loves summer very much, and it really wants to reach outside of "the door of summer". Given the initial position of Natsume and Lennon, please help them to find out the minimum number of human doors that Natsume must open so that Natsume can help Lennon go outside "the door of summer". Initially all the doors are closed.
Input Format
The first line contains an integer T indicating the number of test cases. For each test case, the first line contains two integers N, M denoting the number of rooms and doors respectively (1<=N, M<=100000). The next line contains two integers indicating the initial position of Natsume and Lennon, respectively. In the next M lines, each line contains two adjacent room numbers and a character indicating the type of the door: 'N' for human's door, 'L' for cat's door. If the room number is 0 then that door is one of "the door of summer".
Output Format
For each test case, please output the number of doors that Natsume must open for Lennon.
Sample Input 1
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
1 3
Hints
Problem Source
Migrated from old NTUJ.
Tokyo University contest 2009
Subtasks
| No. | Testdata Range | Score |
|---|