#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
/*
InitG( 3, 2 );
MakeG( 1, 2 );
MakeG( 1, 3 );
*/
if(N <= 3){
if(N == 1){
InitG(1, 0);
}
else{
if(N == 2){
if(M == 0)InitG(2, 0);
else InitG(3, 0);
}
else{
int cur = 4;
f0r(i, M){
int sum = A[i] + B[i];
if(sum == 1)cur++; //draw 0-1
if(sum == 2)cur+=2; //draw 0-2
if(sum == 3)cur+=4; //draw 1-2
}
InitG(cur, 0);
}
}
}
else{
int cnt = 0;
mii encode;
mii decode;
vb visd((1 << 11));
int stupid = 0;
f0r(i, 11){
stupid += (1 << i);
}
visd[stupid] = 1;
encode[0] = stupid;
decode[stupid] = 0;
stupid-=2;
visd[stupid] = 1;
encode[1] = stupid;
decode[stupid] = 1;
stupid+=2;
stupid-=4;
visd[stupid] = 1;
encode[2] = stupid;
decode[stupid] = 2;
stupid += 4;
stupid -= 8;
visd[stupid] = 1;
encode[3] = stupid;
decode[stupid] = 3;
cnt = 4;
f0r(i, (1<<11)){
if(visd[i])continue;
int on = 0;
f0r(j, 11){
if((1 << j) & i)on++;
}
if(on >= 6){
encode[cnt] = i;
decode[i] = cnt;
cnt++;
}
}
vpii edges;
f0r(i, M){
edges.pb(mp(A[i], B[i]));
}
//N to N + 10
//N + 11 to N + 13 as dummy
f0r(i, N){
int ec = encode[i];
f0r(j, 11){
if(ec & (1 << j)){
edges.pb(mp(i, N + j));
}
}
}
FOR(i, N, N + 10){
edges.pb(mp(i, i+1));
}
FOR(i, N, N + 5){
edges.pb(mp(i, N + 11));
}
FOR(i, N + 5, N + 8){
edges.pb(mp(i, N + 12));
}
FOR(i, N + 8, N + 11){
edges.pb(mp(i, N + 13));
}
vi deg(N + 14);
for(auto u : edges){
deg[u.first]++; deg[u.second]++;
}
FOR(i, N, N+11){
// cout<<deg[i]<<' ';
}
// cout<<'\n';
InitG(N + 14, edges.size());
int ct = 0;
for(auto u : edges){
MakeG(ct, u.first, u.second);
ct++;
}
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
/*
InitMap( 3, 2 );
MakeMap( 1, 2 );
MakeMap( 1, 3 );
*/
if(U == 0){
if(V == 1){
InitMap(1, 0);
}
else if(V == 2){
InitMap(2, 0);
}
else if(V == 3){
InitMap(2, 1);
MakeMap(0, 1);
}
else{
int thing = V - 4;
vpii edges;
if(thing & 1){
edges.pb(mp(0, 1));
}
if(thing & 2){
edges.pb(mp(0, 2));
}
if(thing & 4){
edges.pb(mp(1,2));
}
InitMap(3, edges.size());
for(auto u : edges){
MakeMap(u.first,u.second);
}
}
}
else{
int cnt = 0;
mii encode;
mii decode;
vb visd((1 << 11));
int stupid = 0;
f0r(i, 11){
stupid += (1 << i);
}
visd[stupid] = 1;
encode[0] = stupid;
decode[stupid] = 0;
stupid-=2;
visd[stupid] = 1;
encode[1] = stupid;
decode[stupid] = 1;
stupid+=2;
stupid-=4;
visd[stupid] = 1;
encode[2] = stupid;
decode[stupid] = 2;
stupid += 4;
stupid -= 8;
visd[stupid] = 1;
encode[3] = stupid;
decode[stupid] = 3;
cnt = 4;
f0r(i, (1<<11)){
if(visd[i])continue;
int on = 0;
f0r(j, 11){
if((1 << j) & i)on++;
}
if(on >= 6){
encode[cnt] = i;
decode[i] = cnt;
cnt++;
}
}
vi deg(V);
vvi adj(V);
f0r(i, U){
adj[C[i]].pb(D[i]);
adj[D[i]].pb(C[i]);
deg[C[i]]++;
deg[D[i]]++;
}
vi things;
int five;
f0r(i, V){
if(deg[i] <= 5)things.pb(i);
if(deg[i] == 5)five = i;
}
// vout(things);
vi sus;
vb issus(V);
for(auto u : things){
for(auto v : adj[u]){
sus.pb(v);
issus[v] = 1;
}
}
map<int,set<int>>susadj;
mii susdeg;
for(auto u : sus){
for(auto v : adj[u]){
if(issus[v]){
susadj[u].insert(v);
susadj[v].insert(u);
}
}
}
for(auto u : susadj){
susdeg[u.first] = u.second.size();
}
int st;
for(auto u : susdeg){
if(u.second == 1 && find(adj[u.first].begin(), adj[u.first].end(), five) != adj[u.first].end()){
st = u.first;
}
}
int cur = st;
vi gw;
gw.pb(cur);
set<int>vis;
vis.insert(cur);
while(1){
bool f = 0;
for(auto u : susadj[cur]){
if(!vis.count(u)){
cur = u; vis.insert(u); f=1; break;
}
}
if(!f)break;
gw.pb(cur);
}
mii val;
f0r(i, gw.size()){
val[gw[i]] = (1 << i);
}
// vout(gw);
vi label(V, 0);
f0r(i, gw.size()){
for(auto u : adj[gw[i]]){
if(deg[u] > 5 && !issus[u]){
label[u] += val[gw[i]];
}
}
}
vpii edges;
f0r(i, U){
// out2(C[i], D[i]);
if(label[C[i]] != 0 && label[D[i]] != 0){
int r1 = decode[label[C[i]]];
int r2 = decode[label[D[i]]];
edges.pb(mp(r1, r2));
}
}
// vout(label);
/*
out(edges.size());
for(auto u : edges){
out2(u.first, u.second);
}
*/
InitMap(V - 14, edges.size());
for(auto u : edges){
MakeMap(u.first, u.second);
// out2(u.first, u.second);
}
}
}
