#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
void Alice( int n, int m, int A[], int B[] ){
vector<vector<bool>> E(n, vector<bool>(n));
for(int i = 0; i <m; ++i) if(A[i]> B[i]) swap(A[i], B[i]);
for(int i = 0; i <m; ++i) E[A[i]][B[i]] = 1;
vector<pii> P;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(E[i][j]){
P.pb({i, j});
}
}
}
vi ID;
for(int i = 1; i < 1024; i += 2){
ID.pb(i);
}
for(int i = 2; i < 1024; i += 2){
ID.pb(i);
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < 10; ++j){
if((1<<j)&ID[i]) P.pb({i, n + j});
}
}
int t = n + 11;
int s = n + 10;
P.pb({s, t});
for(int i = n; i < n + 10; ++i){
if(i < n + 5) P.pb({s, i});
else P.pb({t, i});
}
for(int i = 0; i < n; ++i) P.pb({i, s}), P.pb({i, t});
P.pb({n + 1, n + 2});
P.pb({n + 2, n + 3});
P.pb({n + 2, n + 4});
P.pb({n + 3, n + 4});
P.pb({n + 6, n + 7});
P.pb({n + 7, n + 8});
P.pb({n + 7, n + 9});
P.pb({n + 8, n + 9});
P.pb({n + 3, n + 8}); // connect 4's
int cnt = 0;
InitG(n + 12, int(P.size()));
for(auto [x, y]: P){
// cerr << x << ' ' << y << '\n';
MakeG(cnt++, x, y);
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
void Bob( int nn, int mm, int C[], int D[] ){
int n = nn - 12;
vi deg(nn);
vector<vector<bool>> E(nn, vector<bool>(nn));
for(int i = 0; i < mm; ++i){
deg[C[i]]++;
deg[D[i]]++;
E[C[i]][D[i]] = E[D[i]][C[i]] = 1;
}
int s = -1, t = -1;
for(int i = 0; i < nn; ++i){
if(deg[i] == 6 + n){
if(s == -1) s = i;
else t = i;
}
}
vi A, B;
for(int i = 0; i < nn; ++i){
if(i == s || i == t) continue;
if(!E[s][i]) A.pb(i);
if(!E[t][i]) B.pb(i);
}
vi degg(nn);
for(int j = 0; j < 5; ++j){
for(int i = 0; i < 5; ++i) degg[A[j]] += E[A[j]][A[i]];
}
sort(all(A), [&](const int &x, const int &y){
return degg[x] < degg[y];
});
swap(A[4], A[2]);
fill(all(degg), 0);
for(int j = 0; j < 5; ++j){
for(int i = 0; i < 5; ++i) degg[B[j]] += E[B[j]][B[i]];
}
sort(all(B), [&](const int &x, const int &y){
return degg[x] < degg[y];
});
swap(B[4], B[2]);
if(E[A[3]][B[3]]){
// np
}else if(E[A[3]][B[4]]){
swap(B[3], B[4]);
}else if(E[A[4]][B[3]]){
swap(A[3], A[4]);
}else{
swap(A[3], A[4]);
swap(B[3], B[4]);
}
if(deg[A[0]] <= deg[B[0]]) swap(A, B);
vi node(n, -1);
vi ID;
for(int i = 1; i < 1024; i += 2){
ID.pb(i);
}
for(int i = 2; i < 1024; i += 2){
ID.pb(i);
}
vi pos(1024);
for(int i = 0; i < ID.size(); ++i) pos[ID[i]] = i;
for(int i = 0; i < nn; ++i){
if(i == s || i == t) continue;
bool in = false;
for(int x: A) in = in | (x == i);
for(int x: B) in = in | (x == i);
if(in) continue;
int sum = 0;
for(int j = 0; j < 5; ++j) sum += (1<<(j)) * E[i][A[j]];
for(int j = 5; j < 10; ++j) sum += (1<<(j)) * E[i][B[j - 5]];
node[pos[sum]] = i;
}
// for(int i = 1; i <= n; ++i){
// cerr << node[i-1] << ' ';
// }
vector<pii> P;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
int v = node[i], u = node[j];
if(E[u][v]) P.pb({i, j});
}
}
// cerr << P.size() << '\n';
InitMap(n, int(P.size()));
for(auto [x, y]: P) MakeMap(x, y);
}
