坑爹啊！！！！！！！当时这道题想了我好久好久 想到各种歪的地方 到最后没有一个地方是想对的 都是想多的 日
怎么说呢 一眼看出是欧拉图问题 但是一开始没想起 异或运算的规则 傻傻的把欧拉路径的算法给敲了一直超时
//顺便稍微写一下异或运算的性质好了 1. 两个相同的数异或得 0 2.0与任意一个数异或 则这个数不变 3. 多个数异或与顺序无关
回归正题 关于欧拉图的性质 简单回顾一下
欧拉通路 所有结点连通并且只有两个结点的 度 为奇数
欧拉回路 所有结点连通并且所有结点的 度 为偶数
另外 欧拉通路的起点和终点固定 欧拉回路的起点（也是终点）任意
这样就可以写了 比完之后关注了一下这道题的博客 感觉他们还是有些逻辑漏洞 然而他们还是A了
AC code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int maxn=100010;
int n,m;
int val[maxn],root[maxn],degree[maxn],sum[maxn];
bool vis[maxn];
void init()
{
for(int i=0;i<=n;i++)
{
root[i]=i;
degree[i]=1;//这里把所有节点的度数初始化1 这样就 最后的度数是否为奇数的判断可以省略
sum[i]=1;//这个图上的连通节点
vis[i]=true;//初始化设置为true
}
}
int fin(int x)
{
return root[x]==x?x:(root[x]=fin(root[x]));
}
int main()
{
int test,u,v,ru,rv;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&n,&m);
init();
for(int i=1;i<=n;i++) scanf("%d",val+i);
while(m--)
{
scanf("%d %d",&u,&v);
degree[u]++;
degree[v]++;
ru=fin(u);
rv=fin(v);
if(ru!=rv)
{
root[ru]=rv;
sum[rv]+=sum[ru];
}
}
int num=0,ans=0,tmp=0,ri,key=1;
for(int i=1;i<=n;i++)
if(degree[i]%2==0) num++; //因为之前把所有节点的 度 初始化为 1 所以这里的判断改成偶数
for(int i=1;i<=n;i++)
{
ri=fin(i);
if(ri!=i)
{
key=ri;//找到一个连通图 并记录其根节点
break;
}
}
for(int i=1;i<=n;i++)
if(fin(i)==i)//对于孤立的节点进行排除
{
tmp++;
vis[i]=false;
}
vis[key]=true;
if(sum[key]+tmp-1!=n||(num!=0&&num!=2))//如果连通图的节点数+孤立点的数目不等于总节点数 那么 必然有另一个连通图 此时必然走不完
//或者不满足欧拉条件 节点度数为奇数（这里为偶数）的个数
{
puts("Impossible");
continue;
}
for(int i=1;i<=n;i++)
{
if(!vis[i]) continue;
if(degree[i]/2%2)//如果经过这个节点有奇数次 则对其进行异或
ans^=val[i];
}
if(num==0)//如果是欧拉回路 那么起点（终点）是任意的 最后再对连通图内的所有节点比较一下
for(int i=1,tmp=ans;i<=n;i++)
if(vis[fin(i)]) ans=max(ans,tmp^val[i]);
printf("%d\n",ans);
}
return 0;
}