#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int,int>


#define repname(a, b, c, d, e, ...) e
#define rep(...)                    repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x)                     for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x)                  for (int i = 0; i < (x); ++i)
#define rep2(i, l, r)               for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c)            for (int i = (l); i < (r); i += (c))





struct ScalarInput {
    template<class T>
    operator T(){
        T ret;
        cin >> ret;
        return ret;
    }
};
struct VectorInput {
    size_t n;
    VectorInput(size_t n): n(n) {}
    template<class T>
    operator vector<T>(){
        vector<T> ret(n);
        for(T &x : ret) cin >> x;
        return ret;
    }
};
ScalarInput input(){ return ScalarInput(); }
VectorInput input(size_t n){ return VectorInput(n); }

template<typename T>
void print(vector<T> a){
  for(int i=0;i<a.size();i++){
    cout<<a[i]<<" \n"[i+1==a.size()];
  }
}

template<class T>
void print(T x){
    cout << x << '\n';
}
 
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail){
  cout << head << ' ';
  print(forward<Tail>(tail)...);
}

#include<atcoder/dsu>
#include<atcoder/modint>
using namespace atcoder;
modint::set_mod(1805972653);
using mint=modint;


int table_size=200000;

vector<mint>fac,finv;

void calc_binom_table(){
  fac.resize(table_size+1);
  finv.resize(table_size+1);
  for(int i=2;i<=table_size;i++){
    fac[i]=fac[i-1]*i;
  }
  finv[table_size]=fac[table_size].inv();
  for(int i=table_size-1;i>=0;i--){
    finv[i]=finv[i+1]*(i+1);
  }
}

mint binom(int n,int k){
  if(n<0||k<0||k>n)return 0;
  return fac[n]*finv[k]*finv[n-k];
}

int N;
vector<mint>MUL(vector<mint>&F,int a,int b){
  vector<mint>G(2*N+1);
  for(int i=0;i+a<=2*N;i++){
    G[i+a]+=F[i];
  }
  for(int i=0;i+b<=2*N;i++){
    G[i+b]+=F[i];
  }
  return G;
}

vector<mint>DIV(vector<mint>&F,int a,int b){
  vector<mint>G(2*N+1);
  if(a==b){
    for(int i=0;i+a<=2*N;i++)G[i]=F[i+a];
    return G;
  }
  int k=abs(a-b);
  int mn=min(a,b);
  for(int i=0;i+mn<=2*N;i++)G[i]=F[i+mn];
  for(int i=0;i+k<=2*N;i++)G[i+k]-=G[i];
  return G;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cerr<<1<<endl;
  mint::set_mod(998244353);

  cerr<<1<<endl;

  fac.resize(table_size+1);
  finv.resize(table_size+1);
  for(int i=2;i<=table_size;i++){
    fac[i]=fac[i-1]*i;
  }
  finv[table_size]=fac[table_size].inv();
  for(int i=table_size-1;i>=0;i--){
    finv[i]=finv[i+1]*(i+1);
  }

  calc_binom_table();

  int M;
  cin>>N>>M;
  vector<array<int,2>>query;
  rep(i,1,2*N)query.push_back({0,i});
  rep(M){
    int a,b;
    cin>>a>>b;
    a--;b--;
    query.push_back({a,b});
  }
  dsu uf(2*N);
  vector<int>col(2*N,0);
  vector<vector<int>>edge(2*N);
  vector<array<int,2>>sz(2*N,{1,0});
  reverse(query.begin(),query.end());
  vector<int>seen(2*N,-1);
  
  vector<mint>F(2*N+1);
  rep(i,2*N+1)F[i]=binom(2*N,i);

  int turn=0;
  for(auto [a,b]:query){
    int a_init=a;
    int b_init=b;
    turn++;
    a=uf.leader(a);
    b=uf.leader(b);
    if(a==b)continue;
    int c0=sz[a][0];
    int c1=sz[a][1];
    int d0=sz[b][0];
    int d1=sz[b][1];
    int S1,S2,T1,T2;

    F=DIV(F,c0,c1);
    F=DIV(F,d0,d1);



    if(col[a]==col[b]){
      S1=c0+d1;
      S2=c1+d0;
      T1=c0+d0;
      T2=c1+d1;
    }
    else{
      S1=c0+d0;
      S2=c1+d1;
      T1=c0+d0;
      T2=c1+d1;
    }

    vector<mint>preF=F;

    F=MUL(F,S1,S2);

    // cout<<BS<<endl;

    // print(col);
    // print(a,b,BS);
    
    uf.merge(a,b);
    bool flag=false;
    if((int)F[N].val()!=0){
      // tigaunidekiru
      if(col[a_init]==col[b_init])flag=true;
    }
    else{
      // muri
      if(col[a_init]!=col[b_init])flag=true;
      F=MUL(preF,T1,T2);
    }


    uf.merge(a,b);
    int root=uf.leader(a);
    int v0=a;
    if(root==a)v0=b;
    vector<int>todo={v0};
    seen[v0]=turn;
    while(!todo.empty()){
      int v=todo.back();
      todo.pop_back();
      if(flag)col[v]^=1;
      sz[root][col[v]]++;
      for(auto u:edge[v]){
        if(seen[u]!=turn){
          seen[u]=turn;
          todo.push_back(u);
        }
      }
    }
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  print(col);
}

answer.code:62:9: fatal error: atcoder/dsu: No such file or directory
   62 | #include<atcoder/dsu>
      |         ^~~~~~~~~~~~~
compilation terminated.