410815: GYM104120 E Exam Period

The exam period is approaching in Huron Academy. Legendary Huron is studying for his math exam and is trying to solve the following problem:

He is given a system of $$$m$$$ expressions with $$$n$$$ variables $$$a_0, a_1, \dots, a_{n-1}$$$. Each expression is of the form:

$$$$$$a_{x_i}+a_{y_i} \square_i c_i$$$$$$

Where $$$c_i$$$ is an integer equal to $$$0$$$, $$$1$$$ or $$$2$$$, and $$$\square_i$$$ is any of the following symbols:

• "=". Which denotes $$$a_{x_i}+a_{y_i} = c_i$$$.
• "!=". Which denotes $$$a_{x_i}+a_{y_i} \neq c_i$$$.
• "<". Which denotes $$$a_{x_i}+a_{y_i} < c_i$$$.
• ">". Which denotes $$$a_{x_i}+a_{y_i} > c_i$$$.
• "<=". Which denotes $$$a_{x_i}+a_{y_i} \leq c_i$$$.
• ">=". Which denotes $$$a_{x_i}+a_{y_i} \geq c_i$$$.

Legendary Huron needs to find out if there are integers $$$a_0, a_1, \dots, a_{n-1}$$$ that satisfies the system of expressions, such that $$$0 \leq a_i \leq 1$$$ for all $$$0 \leq i \leq n-1$$$. Help Legendary Huron to solve this problem.

The first line contains two integres $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 10^5$$$).

The following $$$m$$$ lines contains each two integers $$$x_i$$$ and $$$y_j$$$ ($$$0 \leq x_i, y_i \leq n-1$$$), followed by a string $$$\square_i$$$ ($$$\square_i$$$ is "=", "!=", "<", ">", "<=" or ">=", without the quotation marks) and other integer $$$c_i$$$ ($$$0 \leq c_i \leq 2$$$), denoting that the $$$i$$$-th expression is $$$a_{x_i}+a_{y_i} \square_i c_i$$$.

Print "Yes" (without the quotation marks) if there exists a solution for the system of expressions; otherwise print "No".

3 3
0 1 = 0
1 2 = 1
0 2 = 1

Yes

3 3
0 1 = 0
1 2 = 1
0 2 = 0

No

12 6
0 1 = 2
2 3 != 0
4 5 < 2
6 7 > 1
8 9 <= 1
10 11 >= 0

Yes