#include "testlib.h"
#include <set>
#include <string>

struct disjointSet {
    std::vector<int> p, r;
    disjointSet(int n): p(n), r(n) {
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            r[i] = 0;
        }
    }
    int get(int v) {
        int pv = v;
        while (p[pv] != pv) {
            pv = p[pv];
        }
        while (v != pv) {
            int nv = p[v];
            p[v] = pv;
            v = nv;
        }
        return pv;
    }

    void unite(int a, int b) {
        a = get(a);
        b = get(b);
        if (a != b) {
            if (r[a] == r[b]) {
                ++r[a];
            }
            if (r[a] < r[b]) {
                p[a] = b;
            } else {
                p[b] = a;
            }
        }
    }
};

int main(int argc, char *argv[]) {
    setName("Validator for 'Network Upgrade'");
    registerValidation(argc, argv);

    int n = inf.readInt(2, 10000, "N");
    inf.readEoln();

    std::vector<int> degree(n);
    disjointSet ds(n);

    for (int i = 1; i < n; ++i) {
        int si = inf.readInt(1, n, "s_i");
        inf.readSpace();
        int ti = inf.readInt(si + 1, n, "t_i");
        inf.readEoln();
        if (ds.get(si - 1) == ds.get(ti - 1)) {
            quitf(_fail, "Vertices %d and %d already connected", si, ti);
        }
        ds.unite(si - 1, ti - 1);
        if (++degree[si - 1] == 4) {
            quitf(_fail, "Vertex %d connected 4 times", si);
        }
        if (++degree[ti - 1] == 4) {
            quitf(_fail, "Vertex %d connected 4 times", ti);
        }
    }

    int d = inf.readInt(1, 100000, "D");
    inf.readEoln();

    for (int i = 0; i < d; ++i) {
        int si = inf.readInt(1, n, "s_i");
        inf.readSpace();
        int ti = inf.readInt(si + 1, n, "t_i");
        inf.readSpace();
        inf.readInt(1, 1000000000, "d_i");
        inf.readEoln();
    }

    inf.readEof();
    return 42;
}