codeforces 192e

link: http://codeforces.com/contest/330/problem/E

/*
ID: zypz4571
LANG: C++
TASK: 192e.cpp
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
map<pair<int,int>,bool> coll;
int a[100009];
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif
    int n, m; cin>>n>>m;
    double d=clock(); srand(time(0));
    for (int i = 0, x, y; i < m; ++i) {
        cin>>x>>y; 
        coll.insert(make_pair(make_pair(x,y),true));
        coll.insert(make_pair(make_pair(y,x),true));
    }
    for (int i = 0; i < n; ++i) a[i] = i+1;
    bool t;
    while ((clock()-d)/CLOCKS_PER_SEC < 2.9) {
        random_shuffle(a, a+n);
        a[n] = a[0]; t = false;
        for (int i = 0; i < m; ++i) 
            if (coll[make_pair(a[i],a[i+1])]) {
                t = true; break;
            }
        if (!t) break;
    }
    if (t) printf("-1\n");
    else for (int i = 0; i < m; ++i) printf("%d %d\n", a[i], a[i+1]);
        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

note the use of random_shuffle. the possibility of each try of success is about (1-2/n)^n which is big enough when n is very large so we can use this nondeterminisitic solution.