暴力都能拿最优解，这不合适吧。

gen.cpp如下

#include"testlib.h"
#include<bits/stdc++.h>
using namespace std;
int main(int argc,char *argv[]){
	registerGen(argc,argv,1);
	int n=2e5,m=2e5;
	for(int i=1;i<=n/2;i++)putchar("ab"[i&1]);
	printf("c");
	for(int i=1;i<n/2;i++)putchar("ab"[i&1]);
	for(int l,r;m--;){
		l=rnd.next(1,n),r=rnd.next(1,n);
		if(l>r)swap(l,r);
		printf("%d %d\n",l,r);
	}
}