2-SAT Satisfiability

You are given \(n\) boolean variables \(x_1, x_2, \dots, x_n\) and \(m\) constraints. Each constraint is in the form:

\( (x_i \text{ is } \mathtt{true/false}) \lor (x_j \text{ is } \mathtt{true/false}) \)

For example, a constraint can be "\(x_1\) is true or \(x_3\) is false" or "\(x_7\) is false or \(x_2\) is false".

The goal is to assign each variable a boolean value such that all constraints are satisfied. If an assignment exists, output YES on the first line followed by a line containing the assignments for \(x_1\) to \(x_n\) (each as true or false separated by a single space). Otherwise, output NO.

This is a classic 2-SAT problem.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of variables and the number of constraints, respectively. The variables are numbered from 1 to \(n\).

Each of the following \(m\) lines contains a constraint in the format:

i A j B

Here, i and j are the indices of variables, and A and B are either true or false, indicating that the corresponding literal should be interpreted as \(x_i\) is true/false and \(x_j\) is true/false respectively. The constraint represents the clause: (xi is A) or (xj is B).

outputFormat

If there exists a satisfying assignment, print YES on the first line. In the second line, print \(n\) space-separated boolean values (true or false) corresponding to \(x_1, x_2, \dots, x_n\) respectively.

If no satisfying assignment exists, output a single line with NO.

sample

2 2
1 true 2 false
1 false 2 true

YES
true true