D - X(or)-mas Tree

给定一个树，边权为-1表示未知。给定m个节点间路径异或和二进制1个数的奇偶性，判断能否构造一个合法的树满足条件

• 一个性质：设两个数为x,y。二进制下x有a个1，y有b个1。则：
  • a ^ b = num_1(x ^ y) % 2

所以对于每个边权，我们只需要考虑其1的个数的奇偶性。把m条边加上后一起遍历判断，不确定的边利用异或的性质输出边权即可

注意这里用了内置的位运算函数，简单介绍一下

__builtin_ffs (unsigned int x)返回x的最后一位1的是从后向前第几位，比如7368（1110011001000）返回4

__builtin_clz (unsigned int x)返回前导的0的个数。

__builtin_ctz (unsigned int x) 返回后面的0个个数，和; builtin_clz相对。

__ builtin_popcount (unsigned int x) 返回二进制表示中1的个数。

__builtin_parity (unsigned int x) 返回x的奇偶校验位，也就是x的1的个数模2的结果。

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define fr(a) freopen(a, "r", stdin)
#define fo(a) freopen(a, "w", stdout);
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 200005;
/**/
int t, n, m, err;
int dis[maxn], vis[maxn];
vector<pi>g[maxn];
/**/
void dfs(int u) {
	if(err) return;
	for(auto i:g[u]) {
		int v = i.fi, w = i.se;
		if(dis[v] == -1) {
			dis[v] = dis[u] ^ w;
			dfs(v);
		}
		else if(dis[v] != (dis[u] ^ w)) {
			err = 1;
			return;
		}
	}
}
void solve() {
	err = 0;
	vector< array<int, 3> >ed;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		g[i].clear();
		dis[i] = -1;
	}
	for(int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ed.pb({u, v, w});
		if(w == -1) continue;
		w = __builtin_parity(w);
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	for(int i = 1; i <= n; i++) {
		if(dis[i] == -1) dis[i] = 0, dfs(i);
	}
	if(err) {puts("NO"); return;}
	puts("YES");
	for(auto i: ed) {
		int u = i[0], v = i[1], w = i[2];
		if(w == -1) w = dis[u] ^ dis[v];
		printf("%d %d %d\n", u, v, w);
	}
}
int main()
{
	// fr("test.in");
	// fo("test.out");
	ios::sync_with_stdio(0);cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}