题意就给人一种分治的感觉,把联通块合并。

不妨先对给定的边进行处理,把$x>y$的情况交换一下($x<y$也行,不过要另进行讨论了)。

对于$y$,所有没有用到的边$(x_i,y)$,对于当前递归到的状态,产生贡献的一定是$\min\{x_i\}$

因为由于递归的性质,当前进行的就是最晚的。

反证一下也可以,如果不是$\min\{x_i\}$在当前状态放置,那么它先于一部分的$x_i$与$y$相连,但明显$G$图的编号是连续的,那么也就违背了题意,所以不成立。

因此只要统计出所有的$y$的最小$x_i$即可,这些是对于当前递归状态有贡献的。

引理:如果状态是合法的,其必然存在$siz$,使得$G_1$大小为$siz$,$G_2$大小为$n-siz$,$G_1$与$G_2$的并集恰好是当前状态,且$siz$是唯一的。

证明:由于$[0,siz)$与$[siz,2*siz),[2*siz,3*siz),\cdots$分别对应连边,连续的循环区间大小为$siz$,如果$siz$往左偏移,或往右偏移,都会导致区间不再循环。

处理好$siz$之后,断去两个联通块之间的连边,再当成子问题进行处理。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=1e5+5,M=1e6;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge
{
    int x,y;
    edge(int x=0,int y=0):x(x),y(y){}
    bool operator <(const edge a)const{return x==a.x?y<a.y:x<a.x;}
}a[N];
int L[N];bool v[N];//最小的那个就是当前连边那个 
bool check(int n,int l,int r)
{
    if(n==1)return l==r;
    if(l==r)return 0;
    for(int i=0;i<n;i++)v[i]=0,L[i]=M;
    for(int i=l;i<r;i++)
    {
        int x=a[i].x,y=a[i].y;
        if(L[y]==x)return 0;//重边
        L[y]=min(L[y],x); 
    }
    for(int i=0;i<n;i++)
        if(L[i]==0)v[i]=1;//开头
        else if(L[i]==L[i-1]+1&&v[i-1])v[i]=1;//连续的一段 
    int siz;bool bk;
    for(int i=0;i<n/2;i++)
    {
        siz=i+1;bk=1;
        for(int j=i+siz;j<n;j+=siz)
        {
            if(L[j]==i&&v[j])continue;
            bk=0;break;
        }
        if(bk)break;
    }
    if(!bk)return 0;
    int p1=0,p2=0,i;
    for(i=l;i<r;i++)
    {
        int x=a[i].x,y=a[i].y;
        if(x==siz)break;
        if(y>=siz)continue;//属于两个连通块连接的边都不要了。
        a[p1++]=edge(x,y);
    }p2=p1;
    for(;i<r;i++)
    {
        int x=a[i].x,y=a[i].y;
        a[p2++]=edge(x-siz,y-siz);
    }
    return check(siz,0,p1)&&check(n-siz,p1,p2);
}
int main()
{
    int T;qr(T);
    while(T--)
    {
        int n,m;qr(n),qr(m);
        for(int i=0,x,y;i<m;i++){qr(x),qr(y);if(x>y)swap(x,y);a[i]=edge(x,y);}
        sort(a,a+m);
        if(check(n,0,m))puts("YES");
        else puts("NO");
    }
    return 0;
}