套路地，

考虑dfs树上搞事情

容易发现，对于(x,y)如果dfs树上距离为奇数，或者dfs树上路径中有一条边在某个简单奇环上，那么可以经过奇数条边到达

判断边在某个奇环上：

点双，点双中黑白染色，如果有一个奇环，那么点双中的所有边都在一个奇环中

询问

倍增预处理，LCA搞一下即可

 

#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=500000+5;int n,m;struct node{    int nxt,to;    int id;}e[2*N];int a[N][2];int hd[N],cnt=1;int ok[N],dep[N];int fa[N][20],has[N][20];int blo[N],bls;void add(int x,int y,int d){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].id=d;    hd[x]=cnt;}int dfn[N],low[N];int df;int be[N];int dcc;vector
      
       mem[N];int exi[N];//dcc exi a jihuanint sta[N],top;int ge[N];int rt;void tarjan(int x){//    cout<<" tarjan "<
       
        <
        
         =dfn[x]){                if(fl||x!=rt) ge[x]=1;                fl=true;                ++dcc;                mem[dcc].push_back(x);                int z;                do{                    z=sta[top--];                    mem[dcc].push_back(z);                }while(z!=y);            }        }else low[x]=min(low[x],dfn[y]);    }}int co[N];//white(2) or black(1) or blank(0)int bian[2*N],num;bool fl;void dfs1(int x,int c,int col){    co[x]=col;    for(reg i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(be[y]!=be[x]) continue;        bian[++num]=e[i].id;        if(!co[y]){            dfs1(y,c,col^1);        }else{            if(co[y]==co[x]){                fl=false;            }        }    }}bool vis[N];void dfs2(int x,int d){    dep[x]=d;    vis[x]=1;//    cout<<" dfs2 "<
         
          <<" "<
          
           <
           
            =0;--j){ if(dep[fa[x][j]]>=dep[y]){ lp|=has[x][j]; x=fa[x][j]; } } if(x==y) { if((tmp-2*dep[x])%2==1) return true; if(lp) return true; return false; } for(reg j=19;j>=0;--j){ if(fa[x][j]!=fa[y][j]){ lp|=has[x][j]; lp|=has[y][j]; x=fa[x][j];y=fa[y][j]; } } lp|=has[x][0]|has[y][0]; x=fa[x][0]; if((tmp-2*dep[x])%2==1) return true; if(lp) return true; return false;}int main(){ rd(n);rd(m); int x,y; for(reg i=1;i<=m;++i){ rd(x);rd(y); a[i][0]=x;a[i][1]=y; add(x,y,i);add(y,x,i); } for(reg i=1;i<=n;++i){ if(!dfn[i]){ top=0; ++bls; rt=i; tarjan(i); } } //cout<<" dcc "<
            
             <