#include using namespace std; typedef long long ll; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b #define vl vector #define vii vector> #define vll vector> #define vvi vector> #define vvl vector> #define vvii vector>> #define vvll vector>> #define vst vector #define pii pair #define pll pair #define pb push_back #define all(x) (x).begin(),(x).end() #define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end()) #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005,INF=15<<26; struct UF{ int n; vector par,size,edge; void init(int n_){ n=n_; par.assign(n,-1); size.assign(n,1); edge.assign(n,0); for(int i=0;i>N>>M; UF uf;uf.init(N); vii E(M); vi alive(N,1); for(int i=0;i>a>>b;a--;b--; if(a>b) swap(a,b); E[i]=mp(a,b); alive[a]=false; alive[b]=false; } for(int i=0;i=2){ int s=a+1,t=b-1; if(alive[s]&&alive[t]) uf.unite(s,t); } a+=N; if(a-b>=2){ int s=b+1,t=a-1; if(alive[s%N]&&alive[t%N]) uf.unite(s%N,t%N); } } for(int i=0;i