#PQJ224x4110. QOJ 224_4110

    ID: 2783 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2016欧拉路

QOJ 224_4110

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

输入格式

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

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

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

输出格式

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

对于 100 % 的数据, 𝑇 ≤ 32 , 1 ≤ 𝑁 ≤ 1 000 , 1 ≤ 𝑀 ≤ 10 000 , | 𝑥 | , | 𝑦 | ≤ 100 。