#PQJ224x4110. QOJ 224_4110
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 。