329C - Graph Reconstruction - CodeForces Solution

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> e[100005];
int a[100005],T=1000;
int main(){
	srand(1919810);
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)
    {
		int u,v;
        cin>>u>>v;
		e[u].push_back(v);
        e[v].push_back(u);
	}

	for(int i=1;i<=n;i++) 
     a[i]=i;

	while(T--)
    {
		random_shuffle(a+1,a+n+1);
		bool f=1;
		a[n+1]=a[1];
		for(int i=1;i<=m && f;i++)
        {
			for(int j=0;j<(int)e[a[i]].size();j++)
				if(e[a[i]][j]==a[i+1]) 
                 f=0;
		}
		if(f==1)
        {
			for(int i=1;i<=m;i++) 
               cout<<a[i]<<' '<<a[i+1]<<'\n';
			return 0;
		}
	}
	puts("-1");
}