P4079 [SDOI2016] Gears

There is a transmission system consisting of $N$ compound gears and $M$ chains. Each chain connects two compound gears $u$ and $v$, and provides a transmission ratio $x:y$, meaning that if we consider only these two gears, when gear $u$ turns $x$ turns, gear $v$ will turn $y$ turns. A positive ratio means that if gear $u$ turns clockwise, then gear $v$ also turns clockwise. A negative ratio means that if gear $u$ turns clockwise, then gear $v$ turns counterclockwise. If the transmission ratios provided by different chains are incompatible, some gears cannot turn. We want to know whether all $N$ compound gears in the system can rotate simultaneously. **This transmission system might be disconnected.** That is, it is not guaranteed that any two gears are connected directly or indirectly by chains.

There are multiple test cases. The first line contains an integer $T$, the total number of test cases, followed by $T$ test cases. For each test case, the first line contains two integers $N$ and $M$, the number of gears and the number of chains. Then there are $M$ lines, each describing one chain. Each line contains four integers $u, v, x, y$, meaning that, considering only this linkage, when gear $u$ turns $x$ turns, gear $v$ will turn $y$ turns. It is guaranteed that $x$ is a positive integer and $y$ is a nonzero integer. **Note that $y$ can be negative.**

Output $T$ lines, one for each test case. First, output an identifier indicating the test case index, as shown in the sample output. Then output the decision: if all $N$ compound gears can run simultaneously, output `Yes`; otherwise, output `No`.

Constraints - $1\leq T\leq 32$. - $1\leq N\leq 1000$. - $1\leq M\leq 10^4$. - $1\leq x,|y|\leq 100$. Translated by ChatGPT 5