#include "validator.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(i, a) for(auto& i : a)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 1000;
const int MAXM = 100000;
const int HR = 8;
const int CEO = 15;

bool is_ceo(vector<vector<int> > &graph, int a){
    if(sz(graph[a]) > CEO)return 0;
    int n = sz(graph);
    vector<int> seen(n, 0);
    seen[a] = 1;
    trav(b, graph[a]){
      seen[b] = 1;
      trav(c, graph[b]){
        seen[c] = 1;
      }
    }
    for(int c1 = 0; c1 < n; c1++){
      if(!seen[c1])return 0;
    }
    
    if(sz(graph[a]) <= HR)return 1;

    // sort neighbours wrt degree, hopefully this will speed up validation up a bit
    vector<pair<int,int> > n_pairs;
    trav(b, graph[a]){
      n_pairs.push_back({-sz(graph[b]), b});
    }
    sort(all(n_pairs));

    int cc = 1;
    for(int mask = 0; mask < (1 << sz(graph[a])); mask++){
      if(__builtin_popcount(mask) == HR){
        cc++;
        seen[a] = cc;
        trav(b, graph[a]){
          seen[b] = cc;
        }
        int mask2 = mask;
        int tot = sz(graph[a]) + 1;
        for(int c1 = 0; c1 < sz(graph[a]); c1++){
          if(mask2%2 == 1){
            int i = n_pairs[c1].second;
            trav(c, graph[i]){
              if(seen[c] != cc){
                seen[c] = cc;
                tot++;
                if(tot == n)return 1;
              }
            }
          }
          mask2 /= 2;
        }
        
      }
    }
  return 0;
}

void run() {
  int n = Int(2, MAXN);
  Space();
  int m = Int(1, MAXM);
  Endl();
  
  vector<vector<int> > graph(n, vector<int>());
  set<int> edges;

  for(int c1 = 0; c1 < m; c1++){
     int a = Int(1, n);
     Space();
     int b = Int(1, n);
     assert(a != b);
     Endl();
     a--;
     b--;
     assert(edges.find(a*n+b) == edges.end());
     edges.insert(a*n+b);
     edges.insert(b*n+a);
     graph[a].push_back(b);
     graph[b].push_back(a);
  }

  bool ceo = 0;
  for(int c1 = 0; c1 < n; c1++){
    if(is_ceo(graph, c1)){
      ceo = 1;
      break;
    }
  }
  assert(ceo);

}