硬要卡的话全造大于根号的数据题解里面有的 $3$ 份代码 $5s$ 都跑不过，这题本身理论 $n\sqrt{n}$，就 $3e8$ 了，还要考虑回滚时回溯的超大常数，以及你每次搞一种颜色要插 $2$ 倍的离散化后的值，这只有 $4$ 秒过于抽象了。

如果要 $hack$ 的话，把 $a_i$ 在 $[1,10]$ 里面随都可以随便卡：

//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define ll long long
//#define lll __int128
//#define double long double
using namespace std;
const long long INF=1e16;
//const long long mod=998244353,orm=3;
const long long mod=1000000007;
const int MAXN=5e5+5;
int n,m;
int a[1000005],b[1000005];
mt19937 rnd(unsigned(time(0)));
signed main() {
	freopen("a2.in","w",stdout);
	n=500000,m=500000;printf("%d %d\n",n,m);
	for(int i=1;i<=n;i++) a[i]=rnd()%10+1;
	for(int i=1;i<=n;i++) b[i]=i;random_shuffle(b+1,b+n+1);
	for(int i=1;i<=n;i++) printf("%d ",a[i]);puts("");
	for(int i=1;i<=n;i++) printf("%d ",b[i]);puts("");
	printf("%d %d\n",1,n);
	for(int i=1;i<m;i++) {
		int x=rnd()%n+1,y=rnd()%n+1;
		if(x>y) swap(x,y);
		printf("%d %d\n",x,y);
	}
	return 0;
}