#include "Alicelib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bugz
void Alice( int n, int m, int a[], int b[] ){
int arr[10][10]={
{0,0,0,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0}
};
vector<int> id;
int val[1024];
rep(x,0,1024) if (__builtin_popcount(x)<9) id.pub(x);
rep(x,0,sz(id)) val[id[x]]=x;
vector<ii> v;
rep(x,0,10) rep(y,0,10) if (arr[x][y]) v.pub({n+x,n+y});
rep(x,0,n+10) v.pub({n+10,x});
rep(x,0,n) v.pub({n+11,x});
rep(x,0,m) v.pub({a[x],b[x]});
rep(x,0,n){
rep(y,0,10) if (id[x]&(1<<y)) v.pub({x,n+y});
}
InitG(n+12,sz(v));
rep(x,0,sz(v)) MakeG(x,v[x].fi,v[x].se);
}
#include "Boblib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
bool grid[1030][1030];
int ord[1030];
void Bob( int n, int m, int c[], int d[] ){
int arr[10][10]={
{0,0,0,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0}
};
vector<int> id;
int val[1024];
rep(x,0,1024) if (__builtin_popcount(x)<9) id.pub(x);
rep(x,0,sz(id)) val[id[x]]=x;
rep(x,0,m){
grid[c[x]][d[x]]=true;
grid[d[x]][c[x]]=true;
}
int idx=-1;
int mx=0;
rep(x,0,n){
int deg=0;
rep(y,0,n) if (grid[x][y]) deg++;
if (deg>mx){
mx=deg;
idx=x;
}
}
//cout<<mx<<" "<<idx<<endl;
int idx2;
rep(x,0,n) if (x!=idx && !grid[idx][x]) idx2=x;
//cout<<idx2<<endl;
vector<int> ids;
rep(x,0,n) if (x!=idx2 && x!=idx && !grid[idx2][x]) ids.pub(x);
sort(all(ids));
//for (auto &it:ids) cout<<it<<" "; cout<<endl;
do{
bool can=true;
rep(x,0,10) rep(y,x+1,10){
if (arr[x][y]!=grid[ids[x]][ids[y]]){
can=false;
goto end;
}
}
end:;
if (can) break;
} while (next_permutation(all(ids)));
//for (auto &it:ids) cout<<it<<" "; cout<<endl;
rep(x,0,n) if (x!=idx && x!=idx2){
bool can=true;
rep(y,0,sz(ids)) if (x==ids[y]) can=false;
if (can){
int num=0;
rep(y,0,10) if (grid[x][ids[y]]) num|=(1<<y);
ord[num]=x;
}
}
vector<ii> ans;
rep(x,0,n-12) rep(y,x+1,n-12){
if (grid[ord[val[x]]][ord[val[y]]]) ans.pub({x,y});
}
InitMap(n-12,sz(ans));
for (auto &it:ans) MakeMap(it.fi,it.se);
}
