点和点之间关系密切。考虑刷表然后O(1)回答

暴力：

f[i][j]i到j是否有回文路径，暴力枚举出边。O(m^2)（每个边的对儿会恰好被枚举4次）

优化：

题目只要求“可行性”。考虑在不改变可行性情况下减少边数

提出来所有两边标号相同的边

对于1和0的连通块，如果连通块是二分图，只保留生成树即可（因为连通块内，a到b经过的边的奇偶性确定，至于可能路途遥远一些，但是可以让对称的那一半重复往返走一条边）

如果不是，那么a到b的奇偶性可以是奇数可以是偶数，随便连一个自环即可。

提出来所有两边标号不同的边

这个图显然是二分图

对于这个二分图，保留一个生成树即可

同理也可以在对称的位置来回走

 

 

对于二分图：

1.连通块染色

2.带权并查集

（自环连一个就好了，否则还是会TLE）

// luogu-judger-enable-o2#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pii pair
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=5005;const int M=500000+5;int n,m,q;struct node{ int nxt,to;}e[2*M+2*N];int hd[N],cnt;char s[N];int co[N];void add(int x,int y){ // if(x
           
            qs;void bfs(){ for(reg i=1;i<=n;++i){ f[i][i]=1;qs.push(mk(i,i)); } for(reg i=1;i<=m;++i){ if(co[ex[i]]==co[ey[i]]){ f[ex[i]][ey[i]]=1; f[ey[i]][ex[i]]=1; qs.push(mk(ex[i],ey[i])); } } while(!qs.empty()){ pii now=qs.front();qs.pop(); int x=now.fi,y=now.se; // cout<<" bfs "<
            
             <<" "<
             
              <