The Great Manchu-Han Banquet Challenge

In the Great Manchu-Han Banquet, each contestant is provided with \( n \) distinct ingredients. For each ingredient, the contestant may choose to prepare it in either Manchu style or Han style. There are \( m \) judges, and each judge has two specific dish preferences. A judge's preference is expressed as a pair: one dish prepared in a specified style from a particular ingredient. A contestant passes a judge's evaluation if at least one of the two required dishes is prepared according to the judge's wish.

More formally, label the ingredients from 1 to \( n \). Each contestant must decide, for every ingredient \( i \), a cooking style represented by a boolean value:

[ x_i = \begin{cases} \mathsf{M} & \text{if ingredient } i \text{ is cooked in Manchu style},\ \mathsf{H} & \text{if ingredient } i \text{ is cooked in Han style}. \end{cases} ]

Each judge \( j \) provides two requirements: \((s_{j1}, a_j)\) and \((s_{j2}, b_j)\), where \( s_{j1} \) and \( s_{j2} \) are either M (Manchu style) or H (Han style), and \( a_j, b_j \) are ingredient indices. The judge is satisfied if at least one of the conditions holds:

[ (x_{a_j} = s_{j1}) \text{ or } (x_{b_j} = s_{j2}). ]

Your task is to determine whether there exists an assignment for the \( n \) ingredients such that every judge is satisfied. If such an assignment exists, output YES; otherwise, output NO.

Note: This problem can be modeled as a 2-SAT problem.

inputFormat

The first line contains two integers \( n \) and \( m \) (1 ≤ \( n \) ≤ 10⁵, 1 ≤ \( m \) ≤ 10⁵), representing the number of ingredients and the number of judges, respectively.

Each of the next \( m \) lines contains a judge's preferences in the following format:

s1 a s2 b

Here, s1 and s2 are the style indicators and will be either M (for Manchu style) or H (for Han style). a and b are integers (1-indexed) representing the ingredients.

outputFormat

Output a single line containing either YES if there exists an assignment for the ingredients that satisfies all judges, or NO if no such assignment exists.

sample

3 4
M 1 H 2
M 2 M 3
H 1 H 2
H 1 M 3

YES