题目理解

我们有一个由 $N$ 个齿轮和 $M$ 条链条（边）组成的传动系统。
每条边 $(u, v, x, y)$ 表示：

• 如果 $u$ 转 $x$ 圈，那么 $v$ 转 $y$ 圈。
• 传动比 $x:y$ 的符号表示方向：
  • 正：$u$ 顺时针 → $v$ 顺时针
  • 负：$u$ 顺时针 → $v$ 逆时针

换句话说，我们可以把齿轮的转动用一个实数 $r_i$ 表示（可以是任意实数，表示转速或角度），对于每条边 $(u, v, x, y)$，应满足：

$\frac{r_u}{r_v} = \frac{y}{x}$

因为 $u$ 转 $x$ 圈对应 $v$ 转 $y$ 圈，所以 $r_u \cdot x = r_v \cdot y$ 的另一种写法是 $r_u / r_v = y / x$。

转化为图论问题

我们可以把每个齿轮 $i$ 看作图的一个节点，链条是边。
对于边 $(u, v, x, y)$，我们得到约束：

$r_u \cdot x = r_v \cdot y$

即：

$\frac{r_u}{r_v} = \frac{y}{x}$

如果我们设 $r_1 = 1$（作为参考），那么我们可以用 BFS 或 DFS 遍历图，推导出所有 $r_i$ 相对于 $r_1$ 的值。

具体来说，从节点 $u$ 到节点 $v$ 的传递关系是：

已知 $r_u$，则 $r_v = r_u \cdot \frac{x}{y}$（注意这里 $x$ 是正整数，$y$ 是非零整数，可能是负数）。

检查相容性

当我们遍历图时：

1. 如果某个节点还没有被访问过，就按上述公式计算它的 $r$ 值。
2. 如果某个节点已经被访问过，就检查当前计算出的 $r$ 值是否与之前的值一致（考虑浮点数精度问题，可以用分数形式避免精度误差）。

关键：由于 $y$ 可能是负数，所以传动比可能是负的，表示转动方向相反。
在计算中，负号会导致 $r$ 的正负号变化，表示转动方向。

如果所有推导出的 $r$ 值都满足所有边的约束，则输出 Yes，否则 No。

实现细节

• 为了避免浮点数精度问题，我们可以用分数表示 $r_i$：$(num, den)$，即 $r_i = num/den$，并且保持最简分数形式（用 gcd 约分）。
• 符号由分子分母的符号共同决定。
• 检查一致性时，比较两个分数是否相等：$num1 \cdot den2 == num2 \cdot den1$。
• 注意负数情况。

算法步骤

1. 读入 $T$。
2. 对每组数据：
   • 建图（邻接表），存储 $(to, x, y)$。
   • 初始化 $vis[]$ 为 false，$ratio[]$ 为未定义。
   • 从节点 1 开始 BFS/DFS，设 $ratio[1] = (1, 1)$。
   • 遍历过程中，对于边 $(u, v, x, y)$：
     • 如果 $v$ 未访问，则 $ratio[v] = ratio[u] \cdot (x, y)$ 并约分。
     • 如果 $v$ 已访问，则检查 $ratio[u] \cdot y == ratio[v] \cdot x$ 是否成立，不成立则返回 No。
   • 如果所有边都相容，输出 Yes。