fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int deg[100005]; 
  5. vector<int> p[100005];
  6.  
  7. signed main() {
  8.     int n, m;
  9.     cin >> n >> m;
  10.     int x, y;
  11.     for (int i = 1; i <= m; ++i) {
  12.         cin >> x >> y;
  13.         p[y].push_back(x);
  14.     }
  15.  
  16.     vector<int> a;
  17.     for(int i = 1; i <= n; ++i){
  18.     	a.push_back(i);
  19. 	}
  20.  
  21.     int attempts = 10000;
  22.     while (attempts--) {
  23.         random_shuffle(a.begin(), a.end());
  24.  
  25.         vector<pair<int, int>> res;
  26.         bool check = true;
  27.         for (int i = 1; i < n; ++i) {
  28.             int u = a[i - 1];
  29.             int v = a[i];
  30.             for(int x : p[u]){
  31.             	if(x == v){
  32.             		check = false;
  33.             		break;
  34. 				}
  35. 			}
  36. 			for(int x : p[v]){
  37. 				if(x == u){
  38. 					check = false;
  39. 					break;
  40. 				}
  41. 			}
  42. 			res.push_back({u,v});
  43.         }
  44.         if (check) {
  45.         	if(res.size() > m){
  46.         		int s = m;
  47.         		for (auto e : res) {
  48.         		if(m > 0){
  49.                 cout << e.first << " " << e.second << endl;
  50.                 ++deg[e.first];
  51. 				++deg[e.second];
  52. 				--m; 
  53. 			}
  54.             }
  55. 			}else{
  56.             for (auto e : res) {
  57.                 cout << e.first << " " << e.second << endl;
  58.                 ++deg[e.first];
  59. 				++deg[e.second];  
  60.             }
  61.             if (res.size() < m) {
  62.                 int ans = m - res.size();
  63.                 for (int i = 0; i < n && ans > 0; ++i) {
  64.                     for (int j = i + 2; j < n && ans > 0; ++j) {
  65.                         int u = a[i];
  66.                         int v = a[j];
  67.                         if (deg[u] < 2 && deg[v] < 2) {
  68.                             cout << u << " " << v << endl;
  69.                             deg[u]++;
  70.                             deg[v]++;
  71.                             ans--;
  72.                         }
  73.                     }
  74.                 }
  75.             }
  76.         }
  77.             return 0;
  78.         }
  79.     }
  80.     cout << "-1" << endl;
  81. }
  82.  
Success #stdin #stdout 0.01s 5868KB
comments (?)
stdin
copy 
3 2
1 2
2 3
stdout
copy 
-1
https://ideone.com/ACJkBx
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!