Description

Xiao K has built many farms in MC (Minecraft), a total of $n$, to the point that he has forgotten the exact amount of crops planted in each farm. He only remembers some vague information (a total of $m$ pieces), described in the following three forms:

• Farm $a$ has planted at least $c$ more units of crops than farm $b$.
• Farm $a$ has planted at most $c$ more units of crops than farm $b$.
• Farm $a$ and farm $b$ have planted the same number of crops.

However, because Xiao K’s memory may be inaccurate, he wants to know whether there exists a configuration such that the number of crops in the farms is consistent with all the pieces of information he remembers.

Input Format

The first line contains two integers $n$ and $m$, representing the number of farms and the number of pieces of information remembered by Xiao K.

The next $m$ lines:

• If the first number of a line is $1$, then three integers $a, b, c$ follow, meaning farm $a$ has planted at least $c$ more units of crops than farm $b$.
• If the first number of a line is $2$, then three integers $a, b, c$ follow, meaning farm $a$ has planted at most $c$ more units of crops than farm $b$.
• If the first number of a line is $3$, then two integers $a, b$ follow, meaning farm $a$ has planted the same number of crops as farm $b$.

Output Format

If there exists a configuration consistent with Xiao K’s memory, output Yes, otherwise output No.

3 3
3 1 2
1 1 3 1
2 2 3 2

Yes

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \le n, m, a, b, c \le 5 \times 10^3$.

Translated by ChatGPT 5