设s[x][i]表示从根到x的异或和在第i位上的值（0/1)，(a,b,i)表示a到b的异或和在第i位上的值
那么就有(a,b,i)=(s[a][i]^s[b][i]^s[lca][i]^s[lca][i])=(s[a][i]^s[b][i])
也就是说，能搞出来s[a][i]和s[b][i]的相同或不同关系
用一个并查集，把每个点拆成x和x'，分别表示与x相同和与x不同
若中间出现了矛盾，就是Impossible
若最后同一侧的连通块数>2，就说明答案不唯一
然后对于每一条树上的边(a,b)，如果a和b相同，这个边在第i位上就是0，否则就是1
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+,maxm=2e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int eg[maxn][],id[maxn][][],pct;
int fa[maxn*],N,M;
int flag[maxn*]; inline int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} inline void add(int a,int b){
int x=getf(a),y=getf(b);
if(x!=y) fa[x]=y;
} int main(){
//freopen("","r",stdin);
int i,j,k;
for(int T=rd();T;T--){
N=rd(),M=rd();
bool ans=;pct=;
for(i=;i<=N;i++){
for(j=;j<=;j++)
id[i][j][]=++pct,fa[pct]=pct,id[i][j][]=++pct,fa[pct]=pct;
}
for(i=;i<N;i++)
eg[i][]=rd(),eg[i][]=rd();
for(i=;i<=M;i++){
int a=rd(),b=rd(),w=rd();
for(j=;j<=;j++){
if((w>>(j-))&){
if(getf(id[a][j][])==getf(id[b][j][])) ans=;
add(id[a][j][],id[b][j][]);
add(id[a][j][],id[b][j][]);
}else{
if(getf(id[a][j][])==getf(id[b][j][])) ans=;
add(id[a][j][],id[b][j][]);
add(id[a][j][],id[b][j][]);
}
}
}
if(!ans){
printf("Impossible\n");
continue;
}
CLR(flag,);
for(i=;i<=;i++){
int cnt=;
for(j=;j<=N;j++){
if(!flag[getf(id[j][i][])])
flag[getf(id[j][i][])]=++cnt;
}
if(cnt>){ans=;break;}
}
if(!ans){
printf("No\n");
continue;
}
int mi=1e9,ma=;
for(i=;i<N;i++){
int a=eg[i][],b=eg[i][],x=;
for(j=;j<=;j++){
if(getf(id[a][j][])!=getf(id[b][j][]))
x|=<<(j-);
}
mi=min(mi,x),ma=max(ma,x);
}
printf("%d %d\n",mi,ma);
} return ;
}