#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;

static const uint64_t SEED = 20260807ULL;   // change this to reroll the suite
static const ll MAXN = 100000, MAXM = 200000;

mt19937_64 rng(SEED);
ll rnd(ll lo, ll hi) {                      // inclusive
    assert(lo <= hi);
    return lo + (ll)(rng() % (uint64_t)(hi - lo + 1));
}

// --------------------------------------------------------------------------
struct DSU {
    vector<ll> p, sz;
    DSU(ll n = 0) { init(n); }
    void init(ll n) { p.resize(n); sz.assign(n, 1); iota(p.begin(), p.end(), 0LL); }
    ll find(ll x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    void join(ll a, ll b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
    }
};

// reference solution, used to verify every generated test
int solve(ll n, const vector<array<ll, 3>>& e) {
    DSU d(2 * n + 2);
    for (auto& x : e) {
        ll u = x[0], v = x[1], t = x[2];
        if (t == 1) { d.join(u, v); d.join(u + n, v + n); }
        else        { d.join(u, v + n); d.join(u + n, v); }
    }
    for (ll i = 1; i <= n; i++) if (d.find(i) == d.find(i + n)) return 0;
    return 1;
}

// --------------------------------------------------------------------------
struct Gen {
    ll n;
    vector<int> col;                // the intended group of each agent
    vector<array<ll, 3>> e;
    unordered_set<ll> used;
    DSU conn;                       // connectivity of the constraint graph

    explicit Gen(ll n_) : n(n_), col(n_ + 1), conn(n_ + 2) {
        used.reserve(1 << 19);
        for (ll i = 1; i <= n; i++) col[i] = (int)(rng() & 1);
    }

    ll key(ll u, ll v) const { if (u > v) swap(u, v); return u * (n + 1) + v; }
    bool has(ll u, ll v) const { return used.count(key(u, v)) > 0; }

    bool add(ll u, ll v, int t, bool allowDup = false) {
        if (u == v) return false;
        ll k = key(u, v);
        if (!allowDup) { if (!used.insert(k).second) return false; }
        else used.insert(k);
        e.push_back({u, v, (ll)t});
        conn.join(u, v);
        return true;
    }
    // edge that agrees with the intended colouring
    bool addGood(ll u, ll v, bool allowDup = false) {
        return add(u, v, col[u] == col[v] ? 1 : 0, allowDup);
    }

    // One edge that contradicts constraints already forced by the graph.
    //   mode 0 -> two agents forced into the SAME group, declared to distrust
    //   mode 1 -> two agents forced into DIFFERENT groups, declared to trust
    // mode 1 leaves the t=0 subgraph bipartite, so solutions that only look at
    // distrust edges still answer 1 and get it wrong.
    void addContradiction(int mode, const vector<ll>* pool = nullptr) {
        auto pick = [&]() { return pool ? (*pool)[rnd(0, (ll)pool->size() - 1)] : rnd(1, n); };
        for (ll tries = 0; tries < 50000000LL; tries++) {
            ll u = pick(), v = pick();
            if (u == v) continue;
            if (conn.find(u) != conn.find(v)) continue;   // parity must already be forced
            if (mode == 0 && col[u] != col[v]) continue;
            if (mode == 1 && col[u] == col[v]) continue;
            if (has(u, v)) continue;
            add(u, v, mode == 0 ? 0 : 1);
            return;
        }
        cerr << "addContradiction: no candidate pair found\n";
        exit(1);
    }
};

// --------------------------------------------------------------------------
// builders
// --------------------------------------------------------------------------

// random connected graph: random spanning tree + random extra edges
Gen buildRandomConnected(ll n, ll m) {
    assert(m >= n - 1);
    Gen g(n);
    for (ll i = 2; i <= n; i++) g.addGood(rnd(1, i - 1), i);
    while ((ll)g.e.size() < m) {
        ll u = rnd(1, n), v = rnd(1, n);
        if (u != v) g.addGood(u, v);
    }
    return g;
}

// hamiltonian path + a few long chords; after relabelling this forces a
// traversal of depth ~n, which is what a recursive DFS solution must survive
Gen buildPath(ll n, ll m) {
    assert(m >= n - 1);
    Gen g(n);
    for (ll i = 2; i <= n; i++) g.addGood(i - 1, i);
    while ((ll)g.e.size() < m) {
        ll u = rnd(1, n), v = rnd(1, n);
        if (u != v && llabs(u - v) > n / 4) g.addGood(u, v);
    }
    return g;
}

// near-complete graph on a small vertex set
Gen buildDense(ll n, ll m) {
    Gen g(n);
    vector<pair<int, int>> all;
    all.reserve(n * (n - 1) / 2);
    for (ll i = 1; i <= n; i++)
        for (ll j = i + 1; j <= n; j++) all.push_back({(int)i, (int)j});
    assert((ll)all.size() >= m);
    shuffle(all.begin(), all.end(), rng);
    for (ll k = 0; k < m; k++) g.addGood(all[k].first, all[k].second);
    return g;
}

// many components of varied size, including isolated vertices
Gen buildComponents(ll n, ll m, vector<vector<ll>>& blocks) {
    Gen g(n);
    blocks.clear();
    ll cur = 1;
    while (cur <= n) {
        // ~8% singletons, so the tests really do contain isolated agents
        ll sz = min(n - cur + 1, rnd(1, 100) <= 8 ? 1LL : rnd(2, 400));
        vector<ll> b(sz);
        iota(b.begin(), b.end(), cur);
        blocks.push_back(b);
        cur += sz;
    }
    for (auto& b : blocks)                                   // spanning tree per block
        for (size_t j = 1; j < b.size(); j++) g.addGood(b[rnd(0, (ll)j - 1)], b[j]);
    while ((ll)g.e.size() < m) {                             // extra edges inside blocks
        auto& b = blocks[rnd(0, (ll)blocks.size() - 1)];
        if (b.size() < 2) continue;
        ll u = b[rnd(0, (ll)b.size() - 1)], v = b[rnd(0, (ll)b.size() - 1)];
        if (u != v) g.addGood(u, v);
    }
    return g;
}

// star (one agent of degree n-1) plus many repeated pairs; the contradiction
// is a repeat of an existing pair with the opposite verdict
Gen buildStarWithDuplicates(ll n, ll m) {
    Gen g(n);
    for (ll i = 2; i <= n; i++) g.addGood(1, i);
    while ((ll)g.e.size() < m - 1) {
        ll v = rnd(2, n);
        g.addGood(1, v, /*allowDup=*/true);
    }
    ll v = rnd(2, n);
    g.add(1, v, g.col[1] == g.col[v] ? 0 : 1, /*allowDup=*/true);
    return g;
}

// --------------------------------------------------------------------------
string name(int idx, const char* ext) {
    char buf[64];
    snprintf(buf, sizeof buf, "ezici.%03d.%s", idx, ext);
    return string(buf);
}

void emit(int idx, Gen& g, int expected, const char* note) {
    ll m = (ll)g.e.size();
    assert(1 <= g.n && g.n <= MAXN);
    assert(1 <= m && m <= MAXM);

    // random relabelling + shuffling so no structure leaks through the ordering
    vector<ll> perm(g.n + 1);
    iota(perm.begin(), perm.end(), 0LL);
    shuffle(perm.begin() + 1, perm.end(), rng);

    vector<array<ll, 3>> e = g.e;
    for (auto& x : e) {
        x[0] = perm[x[0]];
        x[1] = perm[x[1]];
        if (rng() & 1) swap(x[0], x[1]);
    }
    shuffle(e.begin(), e.end(), rng);

    for (auto& x : e) {
        assert(1 <= x[0] && x[0] <= g.n);
        assert(1 <= x[1] && x[1] <= g.n);
        assert(x[0] != x[1]);
        assert(x[2] == 0 || x[2] == 1);
    }

    int ans = solve(g.n, e);
    if (ans != expected) {
        cerr << "FATAL: test " << idx << " expected " << expected << ", got " << ans << "\n";
        exit(1);
    }

    string buf;
    buf.reserve((size_t)m * 22 + 32);
    buf += to_string(g.n); buf += ' '; buf += to_string(m); buf += '\n';
    for (auto& x : e) {
        buf += to_string(x[0]); buf += ' ';
        buf += to_string(x[1]); buf += ' ';
        buf += to_string(x[2]); buf += '\n';
    }
    { ofstream in(name(idx, "in"));  in  << buf; }
    { ofstream out(name(idx, "out")); out << ans << '\n'; }

    ll t1 = 0;
    for (auto& x : e) t1 += x[2];
    printf("ezici.%03d  n=%6lld  m=%6lld  trust=%6lld  distrust=%6lld  ans=%d   %s\n",
           idx, g.n, m, t1, m - t1, ans, note);
}

// --------------------------------------------------------------------------
int main() {
    // 001 / 005 -- same shape, differ by one edge
    { Gen g = buildRandomConnected(MAXN, MAXM);
      emit(1, g, 1, "random connected, consistent"); }

    { Gen g = buildRandomConnected(MAXN, MAXM - 1);
      g.addContradiction(0);
      emit(5, g, 0, "random connected + 1 conflict (same group, distrust)"); }

    // 002 / 006 -- long path, forces traversal depth ~1e5
    { Gen g = buildPath(MAXN, MAXN);
      emit(6, g, 1, "hamiltonian path + chord, consistent"); }

    { Gen g = buildPath(MAXN, MAXN - 1);
      g.addContradiction(1);
      emit(2, g, 0, "hamiltonian path + 1 conflict (diff groups, trust)"); }

    // 003 / 007 -- near-complete on a small vertex set
    { Gen g = buildDense(634, MAXM);
      emit(3, g, 1, "near-complete K634, consistent"); }

    { Gen g = buildDense(634, MAXM - 1);
      g.addContradiction(1);
      emit(7, g, 0, "near-complete K634 + 1 conflict (diff groups, trust)"); }

    // 004 / 008 -- many components, isolated vertices
    { vector<vector<ll>> blocks;
      Gen g = buildComponents(MAXN, MAXM, blocks);
      emit(8, g, 1, "many components + isolated vertices, consistent"); }

    { vector<vector<ll>> blocks;
      Gen g = buildComponents(MAXN, MAXM - 1, blocks);
      const vector<ll>* big = nullptr;
      for (auto& b : blocks) if (!big || b.size() > big->size()) big = &b;
      g.addContradiction(0, big);
      emit(4, g, 0, "many components + 1 conflict inside one of them"); }

    // 009 -- star, degree n-1, half the input is repeated pairs
    { Gen g = buildStarWithDuplicates(MAXN, MAXM);
      emit(9, g, 0, "star + duplicated pairs, one repeat contradicts"); }

    // 010 -- minimum size, single distrust edge
    { Gen g(2);
      g.col[1] = 0; g.col[2] = 1;
      g.add(1, 2, 0);
      emit(10, g, 1, "minimum: n=2, m=1, single distrust edge"); }

    return 0;
}