时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
const int _=2005;
int n=10,m=13,q=30,x[_],y[_],o[_],a[_],b[_],c[_];
bool e[_][_];
int main(){
	srand(time(0));
	freopen("policija.in","w",stdout);
	cout<<n<<' '<<m<<'\n';
	for(int i=2;i<=n;i++){
		x[i-1]=rand()%(i-1)+1;
		y[i-1]=i;
		e[x[i-1]][y[i-1]]=e[y[i-1]][x[i-1]]=1;
	}
	for(int i=n;i<=m;i++){
		x[i]=rand()%n+1;
		y[i]=rand()%n+1;
		while(y[i]==x[i]||e[x[i]][y[i]])y[i]=rand()%n+1;
		e[x[i]][y[i]]=e[y[i]][x[i]]=1;
	}
	for(int i=1;i<=m;i++)cout<<x[i]<<' '<<y[i]<<'\n';
	cout<<q<<'\n';
	for(int i=1;i<=q;i++){
		o[i]=rand()%2+1;
		a[i]=rand()%n+1;
		b[i]=rand()%n+1;
		while(a[i]==b[i])b[i]=rand()%n+1;
		cout<<o[i]<<' '<<a[i]<<' '<<b[i]<<' ';
		if(o[i]==2){
			c[i]=rand()%n+1;
			while(c[i]==a[i]||c[i]==b[i])c[i]=rand()%n+1;
			cout<<c[i]<<'\n';
		}else{
			c[i]=rand()%m+1;
			cout<<x[c[i]]<<' '<<y[c[i]]<<'\n';
		}
	}
	return 0;
}