fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <fstream>
  5. const int maxn = 100 * 1000 + 5;
  6. using namespace std;
  7.  
  8. int n, m;
  9. vector<int> G[maxn];
  10. set<int> a;
  11. bool has = false;
  12. int sr[maxn];
  13.  
  14. void back(int poz, int node) {
  15.  
  16.     sr[poz] = node;
  17.     auto it = a.find(node);
  18.     if(it != a.end())
  19.         a.erase(it);
  20.  
  21.     if(poz == m) {
  22.         has = true;
  23.         return;
  24.     }
  25.  
  26.     if(has) return;
  27.  
  28.     if(poz == m - 1) {
  29.         bool ok = true;
  30.         //cerr << "coa";
  31.         for(auto e : G[node])
  32.             if(e == 6)
  33.                 ok = false;
  34.  
  35.         if(ok)
  36.             back(poz + 1, 6);
  37.     }
  38.  
  39.     for(auto v : a) {
  40.         bool ok = true;
  41.  
  42.         for(auto e : G[node])
  43.             if(e == v)
  44.                 ok = false;
  45.  
  46.         if(!ok) continue;
  47.         back(poz + 1, v);
  48.         if(has) return;
  49.     }
  50.  
  51.     a.insert(node);
  52. }
  53. bool mat[50][50];
  54. int grad[500], l[500], r[500];
  55.  
  56. int main() {
  57.  
  58.     //ifstream cin("C.in");
  59.  
  60.     cin >> n >> m;
  61.  
  62.     for(int i = 1; i <= m; ++i) {
  63.         int a, b; cin >> a >> b;
  64.         G[a].push_back(b);
  65.         G[b].push_back(a);
  66.         if(n <= 10) {
  67.             mat[a][b] = true, mat[b][a] = true;
  68.         }
  69.     }
  70.  
  71.     for(int i = 1; i <= n; ++i)
  72.         a.insert(i);
  73.  
  74.     if(n > 7) {
  75.         back(0, 6);
  76.  
  77.         for(int i = 0; i < m; ++i) {
  78.             if(sr[i + 1] == n + 1)
  79.                 sr[i + 1] = 1;
  80.             cout << sr[i] << " " << sr[i + 1] << "\n";
  81.         }
  82.         return 0;
  83.     } else {
  84.         int cnt = 0;
  85.  
  86.         for(int i = 1; i <= n; ++i)
  87.             for(int j = i + 1; j <= n; ++j)
  88.                 if(mat[i][j] == false) {
  89.                     l[++cnt] = i;
  90.                     r[cnt] = j;
  91.                 }
  92.  
  93.         for(int i = 0; i < (1 << cnt); ++i) {
  94.  
  95.             int edges = 0;
  96.             for(int j = 0; j < n; ++j)
  97.                 grad[j + 1] = 0;
  98.  
  99.             for(int j = 0; j < cnt; ++j)
  100.                 if(i & (1 << j)) {
  101.                     grad[l[j + 1]]++;
  102.                     grad[r[j + 1]]++;
  103.                     edges++;
  104.                 }
  105.  
  106.             bool ok = true;
  107.             for(int j = 0; j < n; ++j)
  108.                 if(grad[j + 1] > 2)
  109.                     ok = false;
  110.             //cerr << edges << " " <<  ok << "\n";
  111.  
  112.             if(ok && edges == m) {
  113.                 //cerr << "hai\n";
  114.                 for(int j = 0; j < cnt; ++j)
  115.                     if(i & (1 << j))
  116.                         cout << l[j + 1]<< " " << r[j + 1] << "\n";
  117.                 return 0;
  118.             }
  119.         }
  120.     }
  121.  
  122.     cout << "-1\n";
  123.     return 0;
  124. }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
11 11
10 9
11 10
5 11
5 7
6 7
3 6
2 3
2 9
4 8
1 8
1 4
stdout
copy 
6 1
1 2
2 4
4 3
3 5
5 8
8 9
9 11
11 7
7 10
10 6
https://ideone.com/c5kfDT
language:
C++14 (gcc 8.3)
created:
11 years 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!