题目等价于去掉两条边，使得剩下的图连通，且所有点度数都为偶数。

首先特判掉图一开始就不连通的情况。

求出dfs生成树，对于每条非树边随机一个权值，每条树边的权值为所有经过它的非树边权值的异或和。

那么剩下的图连通等价于两条边权值非$0$，且两条边的权值不等。

如果有$2$个奇点，那么两条边有公共点，枚举公共点判断即可。

否则只能是$4$个奇点，分类讨论判断所有连边方式即可。

时间复杂度$O(n+m)$。

 

#include
     
      #define N 200010int Case,n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed,d[N],vis[N],dfn,f[N],q[N],cnt,ansx,ansy;unsigned long long seed,h[N],tag[N];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y){d[x]^=1;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x,int y){  vis[x]=++dfn;  for(int i=g[x];i;i=nxt[i]){    int u=v[i];    if(u==y)continue;    if(!vis[u])f[u]=i>>1,dfs(u,x);    else if(vis[u]
      
       >1]=seed=seed*233+17;      tag[x]^=seed,tag[u]^=seed;    }  }}void dfs2(int x,int y){  vis[x]=++dfn;  for(int i=g[x];i;i=nxt[i]){    int u=v[i];    if(u==y)continue;    if(!vis[u])dfs2(u,x),tag[x]^=tag[u];  }  if(x>1)h[f[x]]^=tag[x];}inline int get(int x,int y){  for(int i=g[x];i;i=nxt[i])if(v[i]==y)return i>>1;  return 0;}inline void up(int x,int y){  if(!x||!y)return;  if(!h[x]||!h[y]||h[x]==h[y])return;  if(x>y){int z=x;x=y;y=z;}  if(x