C++11(clang++ 3.9) 解法, 执行用时: 353ms, 内存消耗: 1632K, 提交时间: 2019-03-16 12:59:33

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
 
const int maxn = 1E5 + 10;
 
struct E{
	int x,y;
	E(){}
	E(int x,int y): x(x),y(y){}
	bool operator < (const E &b) const {return x < b.x;}
}e[maxn];
 
int t,L[maxn];
bool bo[maxn];
 
bool Judge(int n,int l,int r)
{
	if (n == 1) return l == r;
	if (l == r) return 0;
	for (int i = 0; i < n; i++) 
		L[i] = maxn,bo[i] = 0;
	for (int i = l; i < r; i++) {
		int x = e[i].x;
		int y = e[i].y;
		if (x == L[y]) return 0;
		L[y] = min(L[y],x);
	}
	for (int i = 0; i < n; i++) 
		if (L[i] == 0) bo[i] = 1;
		else if (L[i] - L[i-1] == 1 && bo[i-1]) bo[i] = 1;
	int flag = 0,siz;
	for (int i = 0; i < n/2; i++) {
		siz = i + 1;
		bool ok = 1;
		for (int j = i + siz; j < n; j += siz) {
			if (bo[j] && L[j] == i) continue;
			ok = 0;	break;
		}
		if (ok) {flag = 1; break;}
	}
	if (!flag) return 0;
	int p1 = l,p2;
	for (int i = l; i < r; i++) {
		int x = e[i].x;
		int y = e[i].y;
		if (x == siz) break;
		if (y < siz) e[p1++] = e[i];
	}
	p2 = p1;
	for (int i = l; i < r; i++) {
		int x = e[i].x;
		int y = e[i].y;
		if (x < siz) continue;
		e[p2++] = E(e[i].x - siz,e[i].y - siz);
	}
	return Judge(siz,l,p1) && Judge(n - siz,p1,p2);
}
 
int getint()
{
	char ch = getchar();
	int ret = 0;
	while (ch < '0' || '9' < ch) ch = getchar();
	while ('0' <= ch && ch <= '9')
		ret = ret*10 + ch - '0',ch = getchar();
	return ret;
}
 
int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
	#endif
	
	t = getint();
	while (t--) {
		int n,m;
		n = getint();
		m = getint();
		for (int i = 0; i < m; i++) {
			int x = getint();
			int y = getint();
			e[i] = E(min(x,y),max(x,y));
		} 
		sort(e,e + m);
		if (Judge(n,0,m)) puts("YES");
		else puts("NO");
	}
	return 0;
}