#2069. 「SDOI2016」齿轮

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

现有一个传动系统,包含了 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

数据范围与提示

对于所有的数据, T \leq 32, \ N \leq 1000, \ M \leq10000, \ |x|, |y| \leq 100