<div class="solution-view">
    <div class="row">
        <div class="col-md-6">
            <p>提交时间：2024-12-08 21:07:16</p>
        </div>
        <div class="col-md-6">
            <p>运行 ID: <a href="/solution/detail?id=35361">35361</a></p>
        </div>
    </div>
    <div class="pre"><p>#include&lt;bits/stdc++.h&gt;
#define up(i,l,r) for(int i=(l);i&lt;=(r);++i)
#define down(i,l,r) for(int i=(l);i&gt;=(r);--i)
#define pi pair&lt;int,int&gt;
#define p1 first
#define p2 second
#define m_p make_pair
#define p_b push_back
typedef long long ll;
using namespace std;
const int maxn=9e5+10;
inline ll read(){
    ll x=0;short t=1;char ch=getchar();
    while(ch&lt;&#039;0&#039;||ch&gt;&#039;9&#039;){if(ch==&#039;-&#039;)t=-1;ch=getchar();}
    while(ch&gt;=&#039;0&#039;&amp;&amp;ch&lt;=&#039;9&#039;)x=x*10+ch-&#039;0&#039;,ch=getchar();
    return x*t;
}
int OP,n,m;
vector&lt;pi&gt;E[maxn],fz[maxn];
pi R[maxn],A[maxn];
struct node {
    int S,T;
    vector&lt;int&gt;P;
    void MOD(){
        for(int &amp;x:P)if(x&gt;m)x-=m;
    }
};
struct Graph {
    vector&lt;pi&gt;E[maxn];
    vector&lt;int&gt;P;
    bool vis[maxn];
    void dfs(int u,int fa=-1){
        while(E[u].size()){
            auto it=E[u].back();E[u].pop_back();
            int w=it.p2-(it.p2&gt;m&amp;&amp;it.p2&lt;=2*m)*m;
            if(vis[w])continue;
            vis[w]=1;
            dfs(it.p1,it.p2);
        }
        if(fa!=-1){
            if(!OP)P.p_b(fa);
            else P.p_b(R[fa].p2),P.p_b(R[fa].p1);
        }
    }
    int calc(pi a,pi b){
        map&lt;int,int&gt;mp;
        mp[a.p1]++,mp[a.p2]++,mp[b.p1]++,mp[b.p2]++;
        for(auto it:mp)if(it.p2==2)return it.p1;
        return -1;
    }
    void get_Path(int u,vector&lt;pair&lt;pi,int&gt; &gt;e,vector&lt;node&gt;&amp;Path){Path.clear();
        if(e.empty())return;
        for(auto it:e)E[it.p1.p1].clear(),E[it.p1.p2].clear();
        for(auto it:e)E[it.p1.p1].p_b(m_p(it.p1.p2,it.p2));
        //cerr&lt;&lt;E[u].size()&lt;&lt;endl;
        if(E[u].empty())u=e[0].p1.p1;
        P.clear();dfs(u);
        reverse(P.begin(),P.end());
        //up(i,0,(int)P.size()-1)printf(&quot;%d &quot;,P[i]);printf(&quot;\n&quot;);
        //up(i,0,(int)P.size()-1)printf(&quot;%d %d\n&quot;,A[P[i]].p1,A[P[i]].p2);
        up(i,0,(int)P.size()-1){
            int j=i;
            while(j&lt;(int)P.size()&amp;&amp;P[j]&gt;=1&amp;&amp;P[j]&lt;=2*m)j++;j--;
            if(j==i-1)continue;
            node X;
            if(i==j)X.S=A[P[i]].p1,X.T=A[P[i]].p2;
            else X.S=A[P[i]].p1+A[P[i]].p2-calc(A[P[i]],A[P[i+1]]),X.T=A[P[j]].p1+A[P[j]].p2-calc(A[P[j]],A[P[j-1]]);
            X.P.clear();up(w,i,j)X.P.p_b(P[w]);
            Path.p_b(X);
            i=j+1;
        }
        for(auto it:e)vis[it.p2-(it.p2&gt;m&amp;&amp;it.p2&lt;=2*m)*m]=0;
    }
}T;
bool vis[maxn];
int dep[maxn];
vector&lt;int&gt;P;
vector&lt;pi&gt;son[maxn];
vector&lt;pair&lt;pi,int&gt; &gt;New_e;
int fa[maxn],w[maxn];
int rev(int x){
    if(x&lt;=m)return x+m;
    return x-m;
}
void dfs(int u){
    vis[u]=1;P.p_b(u);
    son[u].clear();
    for(auto it:E[u])if(vis[it.p1]){if(dep[it.p1]&lt;dep[u])fz[it.p1].p_b(m_p(u,rev(it.p2)));}else fa[it.p1]=u,dep[it.p1]=dep[u]+1,w[it.p1]=rev(it.p2),dfs(it.p1),son[u].p_b(it);
}
int deg[maxn];
bool dfs2(int u){
    vector&lt;pair&lt;pi,int&gt; &gt;A;
    for(auto it:son[u])if(dfs2(it.p1))A.p_b(m_p(m_p(u,it.p1),it.p2))/*,cout&lt;&lt;&quot;edge &quot;&lt;&lt;u&lt;&lt;&quot; &quot;&lt;&lt;it.p2&lt;&lt;endl*/;
    for(auto it:fz[u])if(fa[it.p1]!=u)A.p_b(m_p(m_p(u,it.p1),it.p2))/*,cout&lt;&lt;&quot;edge &quot;&lt;&lt;u&lt;&lt;&quot; &quot;&lt;&lt;it.p2&lt;&lt;endl*/;
    while(A.size()&gt;=2){
        auto it1=A.back();A.pop_back();
        auto it2=A.back();A.pop_back();
        if(it1.p1.p2!=u)swap(it1.p1.p1,it1.p1.p2),it1.p2=rev(it1.p2);
        if(it2.p1.p1!=u)swap(it2.p1.p1,it2.p1.p2),it2.p2=rev(it2.p2);
        int M=New_e.size()/2+1;
        New_e.p_b(m_p(m_p(it1.p1.p1,it2.p1.p2),M));++deg[it1.p1.p1],++deg[it2.p1.p2];
        New_e.p_b(m_p(m_p(it2.p1.p2,it1.p1.p1),M+m));
        R[M]=m_p(it1.p2,it2.p2);
        R[M+m]=m_p(it2.p2,it1.p2);
    }
    if(A.size()){
        auto it1=A.back();A.pop_back();
        auto it2=m_p(m_p(u,fa[u]),w[u]);
        if(it1.p1.p2!=u)swap(it1.p1.p1,it1.p1.p2),it1.p2=rev(it1.p2);
        if(it2.p1.p1!=u)swap(it2.p1.p1,it2.p1.p2),it2.p2=rev(it2.p2);
        int M=New_e.size()/2+1;
        New_e.p_b(m_p(m_p(it1.p1.p1,it2.p1.p2),M));++deg[it1.p1.p1],++deg[it2.p1.p2];
        New_e.p_b(m_p(m_p(it2.p1.p2,it1.p1.p1),M+m));
        R[M]=m_p(it1.p2,it2.p2);
        R[M+m]=m_p(it2.p2,it1.p2);
        return 0;
    }
    return 1;
}
void slv(){
    n=read(),m=read();
    up(i,1,n)vis[i]=0,E[i].clear(),fz[i].clear();
    up(i,1,m){
        int x=read(),y=read();
        A[i]=m_p(x,y);A[i+m]=m_p(y,x);
        E[x].p_b(m_p(y,i)),E[y].p_b(m_p(x,i+m));
    }
    vector&lt;node&gt;ans;
    up(i,1,n)if(!vis[i]){
        P.clear();dfs(i);
        for(int x:P)deg[x]=0;
        if(!OP){
            vector&lt;pair&lt;pi,int&gt; &gt;e;
            for(int x:P)for(auto it:E[x])e.p_b(m_p(m_p(x,it.p1),it.p2));
            int p=0;
            for(int x:P)if(E[x].size()&amp;1)++p,e.p_b(m_p(m_p(n+1,x),m*2+p)),e.p_b(m_p(m_p(x,n+1),m*2+p)),A[m*2+p]=m_p(n+1,x);
            vector&lt;node&gt;v;
            T.get_Path(n+1,e,v);
            for(auto &amp;x:v)x.MOD();
            for(auto x:v)ans.p_b(x);
        }else {
            vector&lt;pair&lt;pi,int&gt; &gt;e;
            for(int x:P)for(auto it:E[x])e.p_b(m_p(m_p(x,it.p1),it.p2));
            if((e.size()/2)&amp;1){printf(&quot;0\n&quot;);return;}
            New_e.clear();dfs2(i);
            int p=0;
            //for(int x:P)cout&lt;&lt;deg[x]&lt;&lt;&quot; &quot;;cout&lt;&lt;endl;
            for(int x:P)if(deg[x]&amp;1)++p,New_e.p_b(m_p(m_p(n+1,x),m*2+p)),New_e.p_b(m_p(m_p(x,n+1),m*2+p)),A[m*2+p]=m_p(n+1,x),R[m*2+p]=m_p(0,0);
            //assert(New_e.size()&lt;=m);
            //for(int x:P)printf(&quot;%d %d\n&quot;,fa[x],x);
            //up(j,1,int(New_e.size())/2)printf(&quot;??? %d %d\n&quot;,R[j].p1,R[j].p2);printf(&quot;\n&quot;);
            vector&lt;node&gt;v;
            T.get_Path(n+1,New_e,v);
            for(auto &amp;x:v)x.MOD();
            for(auto x:v)ans.p_b(x);
        }
    }/*printf(&quot;%d\n&quot;,(int)ans.size());
    for(auto it:ans){
        printf(&quot;%d %d %d\n&quot;,it.S,it.T,(int)it.P.size());
        for(int x:it.P)printf(&quot;%d &quot;,x);printf(&quot;\n&quot;);
    }*/
    printf(&quot;1\n&quot;);
}
int main(){
    //freopen(&quot;run.in&quot;,&quot;r&quot;,stdin);
    //freopen(&quot;run.out&quot;,&quot;w&quot;,stdout);
    int t=read();OP=read();while(t--)slv();
    fclose(stdin);
    fclose(stdout);
    return 0;
}</p></div>
</div>
<script type="text/javascript">
    (function ($) {
        $(document).ready(function () {
            $('.pre p').each(function(i, block) {  // use <pre><p>
                hljs.highlightBlock(block);
            });
        })
    })(jQuery);
</script>