设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

1 #include
     
       2 #define pa pair
      
        3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6 const int maxn=1e5+10,maxm=2e5+10; 7  8 inline ll rd(){ 9     ll x=0;char c=getchar();int neg=1;10     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();}11     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();12     return x*neg;13 }14 15 int eg[maxn][2],id[maxn][20][2],pct;16 int fa[maxn*40],N,M;17 int flag[maxn*40];18 19 inline int getf(int x){
   return x==fa[x]?x:fa[x]=getf(fa[x]);}20 21 inline void add(int a,int b){22     int x=getf(a),y=getf(b);23     if(x!=y) fa[x]=y;24 }25 26 int main(){27     //freopen("","r",stdin);28     int i,j,k;29     for(int T=rd();T;T--){30         N=rd(),M=rd();31         bool ans=1;pct=0;32         for(i=1;i<=N;i++){33             for(j=1;j<=16;j++)34                 id[i][j][0]=++pct,fa[pct]=pct,id[i][j][1]=++pct,fa[pct]=pct;35         }36         for(i=1;i
       
        >(j-1))&1){42                     if(getf(id[a][j][0])==getf(id[b][j][0])) ans=0;43                     add(id[a][j][0],id[b][j][1]);44                     add(id[a][j][1],id[b][j][0]);45                 }else{46                     if(getf(id[a][j][0])==getf(id[b][j][1])) ans=0;47                     add(id[a][j][0],id[b][j][0]);48                     add(id[a][j][1],id[b][j][1]);49                 }50             }51         }52         if(!ans){53             printf("Impossible\n");54             continue;55         }56         CLR(flag,0);57         for(i=1;i<=16;i++){58             int cnt=0;59             for(j=1;j<=N;j++){60                 if(!flag[getf(id[j][i][0])])61                     flag[getf(id[j][i][0])]=++cnt;62             }63             if(cnt>2){ans=0;break;}64         }65         if(!ans){66             printf("No\n");67             continue;68         }69         int mi=1e9,ma=0;70         for(i=1;i