AC

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

struct Edge {

int to;
int x, y;

};

class GearSystem { private:

int n, m;
vector<vector<Edge>> graph;
vector<bool> visited;
vector<pair<long long, long long>> speed; // 速度表示为分数 (分子, 分母)

// 求最大公约数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 分数化简
void simplify(pair<long long, long long>& frac) {
    long long g = gcd(abs(frac.first), abs(frac.second));
    frac.first /= g;
    frac.second /= g;
    if (frac.second < 0) {
        frac.first = -frac.first;
        frac.second = -frac.second;
    }
}

// 分数乘法
pair<long long, long long> multiply(const pair<long long, long long>& a, 
                                   const pair<long long, long long>& b) {
    pair<long long, long long> result;
    result.first = a.first * b.first;
    result.second = a.second * b.second;
    simplify(result);
    return result;
}

// 检查两个分数是否相等
bool equal(const pair<long long, long long>& a, 
          const pair<long long, long long>& b) {
    return a.first * b.second == a.second * b.first;
}

public:

GearSystem(int n, int m) : n(n), m(m) {
    graph.resize(n + 1);
    visited.assign(n + 1, false);
    speed.resize(n + 1, {0, 1});
}

void addEdge(int u, int v, int x, int y) {
    graph[u].push_back({v, x, y});
    graph[v].push_back({u, y, x}); // 注意这里交换了x,y
}

bool dfs(int u) {
    visited[u] = true;
    
    for (const Edge& edge : graph[u]) {
        int v = edge.to;
        
        // 计算v应该有的速度
        pair<long long, long long> expectedSpeed;
        if (edge.y > 0) {
            expectedSpeed = multiply(speed[u], {edge.y, edge.x});
        } else {
            expectedSpeed = multiply(speed[u], {-edge.y, edge.x});
            expectedSpeed.first = -expectedSpeed.first; // 处理负号
        }
        simplify(expectedSpeed);
        
        if (!visited[v]) {
            speed[v] = expectedSpeed;
            if (!dfs(v)) {
                return false;
            }
        } else {
            // 检查是否与已有值一致
            if (!equal(speed[v], expectedSpeed)) {
                return false;
            }
        }
    }
    return true;
}

bool canRotate() {
    // 遍历所有连通分量
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            speed[i] = {1, 1}; // 设参考速度为1
            if (!dfs(i)) {
                return false;
            }
        }
    }
    return true;
}

};

int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;

for (int caseNum = 1; caseNum <= T; caseNum++) {
    int N, M;
    cin >> N >> M;
    
    GearSystem system(N, M);
    
    for (int i = 0; i < M; i++) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        system.addEdge(u, v, x, y);
    }
    
    bool result = system.canRotate();
    cout << "Case #" << caseNum << ": " << (result ? "Yes" : "No") << endl;
}

return 0;

}