题目描述

给定 $n$ 个整数变量 $x_1, x_2, \ldots, x_n$，以及 $m$ 条约束条件，判断是否存在一组整数赋值满足所有约束。

约束有三种类型：

• 类型 1：$x_a \ge x_b + c$（变量 $a$ 比变量 $b$ 至少大 $c$）；
• 类型 2：$x_a \le x_b + c$（变量 $a$ 比变量 $b$ 至多大 $c$）；
• 类型 3：$x_a = x_b$（变量 $a$ 和变量 $b$ 相等）。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示变量个数和约束条数。

接下来 $m$ 行，每行描述一条约束：

• 若第一个数为 $1$，后跟三个整数 $a, b, c$，表示 $x_a \ge x_b + c$；
• 若第一个数为 $2$，后跟三个整数 $a, b, c$，表示 $x_a \le x_b + c$；
• 若第一个数为 $3$，后跟两个整数 $a, b$，表示 $x_a = x_b$。

输出格式

如果存在满足所有约束的整数赋值，输出 Yes，否则输出 No。

样例

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

Yes

提示

对于 $100\%$ 的数据，$1 \le n, m, a, b, c \le 5 \times 10^3$。