#include using namespace std; struct DSU { vector parent; DSU(int N) { parent.resize(N); for (int i = 0; i < N; i++) parent[i] = i; } int findParent(int u) { return parent[u] = parent[u] == u ? u : findParent(parent[u]); } void merge(int u, int v) { int pu = parent[u], pv = parent[v]; if (rand() % 2 == 0) { parent[pu] = pv; } else { parent[pv] = pu; } } }; typedef pair> Edge; struct Graph { vector > > g; set edges; vector parity; Graph(int N) { g.resize(N); parity.resize(N); } void addEdge(int from, int to, int wt) { if (from > to) { swap(from, to); } assert(edges.find(make_pair(wt, make_pair(from, to))) == edges.end()); edges.insert(make_pair(wt, make_pair(from, to))); g[from].push_back(make_pair(to, wt)); g[to].push_back(make_pair(from, wt)); } set findSpanningTree() { set res; DSU dsu(g.size()); for (auto it: edges) { int from = it.second.first, to = it.second.second, wt = it.first; if (dsu.findParent(from) != dsu.findParent(to)) { dsu.merge(from, to); res.insert(it); } } return res; } void dfs(int from, int par = -1) { for (auto it: g[from]) { int to = it.first, wt = it.second; if (to != par) { parity[to] = parity[from] ^ wt; dfs(to, from); } } } void genParity() { dfs(0); } int getParity(int from, int to) { return parity[from] ^ parity[to]; } int check() { set spanningTreeEdges = findSpanningTree(); Graph tree(g.size()); for (auto it: spanningTreeEdges) { int from = it.second.first, to = it.second.second, wt = it.first; tree.addEdge(from, to, wt); } tree.genParity(); for (auto it: edges) { int from = it.second.first, to = it.second.second, wt = it.first; if (!spanningTreeEdges.count(it) && tree.getParity(from, to) != wt) { return false; } } return true; } }; const int MAX = (int) 1e5; const int MAXS = (int) 1e6; char buf[MAX]; int main() { int T, sumN = 0, sumQ = 0; scanf("%d", &T); assert(T >= 1 && T <= MAXS); while (T--) { int N, Q; scanf("%d %d", &N, &Q); assert(N >= 1 && N <= MAX); assert(Q >= 1 && Q <= MAXS); sumN += N; sumQ += Q; map, int> mp; int ok = true; for (int i = 0; i < Q; i++) { int u, v, parity; scanf("%d %d %d", &u, &v, &parity); assert(u >= 1 && u <= N); assert(v >= 1 && v <= N); assert(parity >= 0 && parity <= 1); u--; v--; if (u > v) { swap(u, v); } if (mp.find({u, v}) != mp.end() && mp[{u, v}] != parity) { ok = false; } mp[make_pair(u, v)] = parity; } if (ok) { Graph g(N); for (auto it: mp) { g.addEdge(it.first.first, it.first.second, it.second); } ok = g.check(); } puts(ok ? "yes" : "no"); } cerr << "sumQ " << sumQ << endl; assert(sumN >= 1 && sumN <= MAXS); assert(sumQ >= 1 && sumQ <= MAXS); scanf("%s", buf); assert(strlen(buf) == 0); return 0; }