Map Reduce

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

'MapReduce' is a framework for processing parallelizable problems across huge datasets using a large number of computers (nodes). When you submit a task to cluster, the master node would assign "Map" and "Reduce" function to each nodes.
To simplified the model, you can assume there are N nodes (index from 1 to N) in the cluster except master node. Each node should be either a "Mapper" or a "Reducer". And "Mapper" and "Reducer" node is also indispensable in the cluster when we use this framework. In practical work, we found a dissatisfied problem: due to the unknown reason, when we assign a specific role to node X, and a specific role to another node Y, web connection would be broken. According to long-term observation on this cluster, we found M pairs of "trouble maker" as described above. 
Today I received a new task, and I want to take whole cluster into use, which mean each node should be assigned a role. Given all information about the cluster, I want to know whether it is possible for me to establish a MapReduce model.

Input

The first line of input file contains an integer T indicating the number of case.
In each test case:
The first line contains two integers N and M. (2 <= N, M <= 100)
The next M line, each line contains a pair of "trouble maker" in the form of "X A Y B". X and Y are the index of two nodes, while A and B are name of role. It means when assign role A to X and role B to Y, the web connection would be broken. A and B can be either "M" or "R" which indicate the "Mapper" and "Reducer" respectively. (1 <= X, Y <= N)

Output

For each test case:
You should output "Yes" if it is possible to finish the task; otherwise, output "No".

Sample Input

2
2 1
1 M 2 M
2 2
1 M 2 R
1 R 2 R

Sample Output

Yes
Yes

Source

dut200901102

Manager

Information
Solved Number14
Submit Number80
Problem Tags
2-sat
graphs
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel