#include "validator.h"

// Example validator for the format:
// n m k
// a_1 a_2 ... a_n (1 <= a_i <= k)
// u_1 v_1
// ...
// u_m v_m

void run() {
	int V = Int(3, 3000); Space();
	int E = Int(3, 6000); Endl();

    set<pair<int, int>> ed;

    vector<vector<int>> G(V);
	for (int i = 0; i < E; i++) {
		int a = Int(1, V); Space();
		int b = Int(1, V); Endl();
        --a; --b;
		assert(a != b);
        ed.emplace(a, b);
        ed.emplace(b, a);
        G[a].push_back(b);
        G[b].push_back(a);
	}
    assert((int)ed.size() == 2*E);

    vector<bool> seen(V);
    function<pair<int,int>(int)> dfs = [&](int at) {
        if (seen[at]) return make_pair(0, 0);
        seen[at] = true;
        int vs = 1;
        int es = (int)G[at].size();
        for (int v : G[at]) {
            auto [cvs, ces] = dfs(v);
            vs += cvs;
            es += ces;
        }
        return make_pair(vs, es);
    };

    bool nontree = false;
    for (int i = 0; i < V; i++) {
        if (!seen[i]) {
            auto [vs, es] = dfs(i);
            es /= 2;
            if (vs > 1) {
                assert(es >= vs - 1);
                if (es > vs - 1) nontree = true;
            }
        }
    }
    assert(nontree);
}