QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 4110. 齿轮

统计

现有一个传动系统,包含了 $N$ 个组合齿轮和 $M$ 个链条。每一个链条连接了两个组合齿轮 $u$ 和 $v$,并提供了一个传动比 $x:y$。即如果只考虑这两个组合齿轮,编号为 $u$ 的齿轮转动 $x$ 圈,编号为 $v$ 的齿轮会转动 $y$ 圈。传动比为正表示若编号为 $u$ 的齿轮顺时针转动,则编号为 $v$ 的齿轮也顺时针转动。传动比为负表示若编号为 $u$ 的齿轮顺时针转动,则编号为 $v$ 的齿轮会逆时针转动。若不同链条的传动比不相容,则有些齿轮无法转动。我们希望知道,系统中的这 $N$ 个组合齿轮能否同时转动。

输入格式

有多组数据,第一行给定整数 $T$,表示总的数据组数,之后依次给出 $T$ 组数据。

每一组数据的第一行给定整数 $N$ 和 $M$,表示齿轮总数和链条总数。

之后有 $M$ 行,依次描述了每一个链条,其中每一行给定四个整数 $u$,$v$,$x$ 和 $y$,表示只考虑这一组联动关系的情况下,编号为 $u$ 的齿轮转动 $x$ 圈,编号为 $v$ 的齿轮会转动 $y$ 圈。请注意,$x$ 为正整数,而 $y$ 为非零整数,但是 $y$ 有可能为负数。

输出格式

输出 $T$ 行,对应每一组数据。首先应该输出标识这是第几组数据,参见样例输出。之后输出判定结果,如果 $N$ 个组合齿轮可以同时正常运行,则输出 Yes,否则输出 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

子任务

对于 $30\%$ 的数据,$N \leq 10$,$M \leq 18$。

对于 $100\%$ 的数据,$T \leq 32$,$1 \leq N \leq 1\,000$,$1 \leq M \leq 10\,000$, $ |x|, |y| \leq 100$。