Description

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

Input

有多组数据, 第一行给定整数 \(T\), 表示总的数据组数, 之后依次给出 \(T\) 组数据.

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

Output

输出 \(T\) 行, 对应每一组数据. 首先应该输出标识这是第几组数据, 参见样例输出. 之后 输出判定结果, 如果 \(n\) 个组合齿轮可以同时正常运行, 则输出 Yes, 否则输出 No.

Sample Input

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

Sample Output

Case #1: Yes
Case #2: No

Data Range

对于所有数据, 满足:\(T \leq 32, N \leq 1000, M \leq 10000, |x - y| \leq 100\)

Explanation

好吧, 看到这道题就想起某一年做过的 “食物链”. 食物链是维护一个并查集, 来进行差分查询. 这里我们只需要考虑它们之间的传动比, 所以维护的其实是一个路径压缩的并查集, 中间存上相对传动比. 我差点把它看成按秩合并了~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 2010;
const llf epsilon = 1e-8;

class UnionFindSet
{
public:
    int n, par[maxn], size[maxn];
    llf ratio[maxn];
    int find(int p)
    {
        if (p == par[p])
            return p;
        int q = par[p];
        par[p] = find(q);
        ratio[p] *= ratio[q];
        return par[p];
    }
    bool join(int p, int q, llf rate = 1.0)
    {
        int p_ = find(p),
            q_ = find(q);
        if (p_ == q_) {
            if (fabs(ratio[p] / ratio[q] - rate) > epsilon)
                return false;
            return true;
        }
        if (size[p_] > size[q_]) {
            swap(p_, q_);
            swap(p, q);
            rate = 1.0 / rate;
        }
        par[p_] = q_;
        size[q_] += size[p_];
        ratio[p_] = ratio[q] / ratio[p] * rate;
        return true;
    }
    bool compatible(int p, int q, llf rate = 1.0)
    {
        int p_ = find(p), q_ = find(q);
        if (p_ != q_)
            return true;
        if (fabs(ratio[p] / ratio[q] - rate) > epsilon)
            return false;
        return true;
    }
    void init(int n_)
    {
        n = n_;
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            size[i] = 1;
            ratio[i] = 1.0;
        }
        return ;
    }
} ufs;

int T, n, m;

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d", &n, &m);
        ufs.init(n);
        bool failed = false;
        for (int i = 1; i <= m; i++) {
            int u, v, x, y;
            scanf("%d%d%d%d", &u, &v, &x, &y);
            if (!ufs.compatible(u, v, 1.0 * x / y))
                failed = true;
            else
                ufs.join(u, v, 1.0 * x / y);
        }
        printf("Case #%d: %s\n", idx, failed ? "No" : "Yes");
    }
    return 0;
}