Description

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.

Input Format

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 Format

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.

2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7

Case #1: Yes
Case #2: No

Hint

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