main.cpp

#include <bits/stdc++.h>
using namespace std;

vector<string> crop(string& s) {
    vector<string> vec;
    string cur = "";

    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] < 'a' || s[i] > 'z') {
            // if s[i] is not a lowercase english letter
            if (!cur.empty()) {
                vec.push_back(cur);
                cur = "";
            }
        } else {
            cur.push_back(s[i]);
        }
    }

    return vec;
}

bool solve() {
    int n;
    cin >> n;

    vector<string> sources(n);  // source lines
    map<string, int> indexes;   // map of "variable name" -> "index"
    vector< vector<string> > deps_raw(n);   // list of dependencies (as variable string)
    vector< set<int> > deps(n);   // list of dependencies (as indexes)

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        sources[i] = s;

        vector<string> variables = crop(s);
        string name = variables[0];
        indexes[name] = i;

        vector<string> var_names;
        for (int z = 2; z < (int) variables.size(); z++)
            var_names.push_back(variables[z]);
        deps_raw[i] = var_names;
    }

    for (int i = 0; i < n; i++) {
        for (auto dep : deps_raw[i]) {
            if (!indexes.count(dep))
                return false;
        }
    }

    for (int i = 0; i < n; i++) {
        set<int> deps_set;
        for (auto dep : deps_raw[i])
            deps_set.insert(indexes[dep]);
        deps[i] = deps_set;
    }

    // main loop here!
    vector<bool> used(n);
    for (int count = 0; count < n; count++) {
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (used[i])
                continue;
            if (deps[i].empty()) {
                v = i;
                break;
            }
        }
        if (v == -1)
            return false;

        cerr << count << "-th line: " << sources[v] << endl;

        used[v] = true;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                if (deps[i].count(v))
                    deps[i].erase(v);
            }
        }
    }

    return true;
}

int main(int argc, char *argv[]) {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cout << "Case #" << i + 1 << ": ";
        cerr << "Test #" << i + 1 << endl;
        cout << (solve() ? "GOOD" : "BAD") << endl;
    }
}