#include "Alicelib.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pair<ll, ll>> e;
for (ll i=0; i<M; i++){
e.push_back({A[i], B[i]});
}
ll offs=0;
vector<ll> cnt(10);
for (ll i=0; i<N; i++){
for(ll j=0; j<10; j++) if (i&(1<<j)) cnt[j]++;
}
if (cnt[0]==cnt[9]){
offs=1; assert(0);
}
for (ll i=offs; i<N+offs; i++){
for (ll j=0; j<10; j++){
if ((i&(1<<j))) e.push_back({i-offs, N+j});
}
e.push_back({i-offs, N+11});
}
for (ll j=0; j<10; j++) e.push_back({N+j, N+10});
for (ll j=0; j<10; j++) e.push_back({N+j, N+11});
for (ll j=1; j<10; j++) e.push_back({N+j, N+j-1});
InitG(N+12, e.size());
for (ll i=0; i<(ll)e.size(); i++){
// cout << e[i].first << " " << e[i].second << endl;
MakeG(i, e[i].first, e[i].second);
}
}
#include "Boblib.h"
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
// cout << V << "-" << U << endl;
vector<vector<ll>> A(V);
ll n = V-12;
ll offs=0;
vector<ll> cnt(10);
for (ll i=0; i<n; i++){
for(ll j=0; j<10; j++) if (i&(1<<j)) cnt[j]++;
}
if (cnt[0]==cnt[9]){
offs=1; assert(0);
}
for (ll i=0; i<U; i++){
A[C[i]].push_back(D[i]); A[D[i]].push_back(C[i]);
}
ll r1=-1, r2=-1; set<ll> usd;
for (ll i=0; i<V; i++) usd.insert(i);
for (ll i=0; i<V; i++){
if ((ll)A[i].size()==V-2){
r1=i; for (auto v:A[i]){
usd.erase(v);
}
usd.erase(i);
r2 = *usd.begin();
break;
}
}
assert(r1!=-1 and r2!=-1);
set<ll> bits;
for (auto v:A[r2]) bits.insert(v);
// cout << A[r2].size() << endl;
// for (auto ch:A[r2]) {
// cout << ch << ": ";
// for (auto x:A[ch]){
// cout << x << " ";
// }
// cout << endl;
// }
// cout << endl;
assert(A[r2].size()==10);
vector<ll> bpos; ll cur=r1;
// for (auto v:A[r2]) {
// cout << v << ": ";
// for (auto ch:A[v]) cout << ch << " ";
// cout << endl;
// }
// cout << endl;
// cout << r1 << " " << r2 << endl;
while (!bits.empty()){
// cout << cur << endl;
bool hp=0;
for (auto v:A[cur]){
if (bits.count(v)){
cur=v; bpos.push_back(v);
bits.erase(v); hp=1;break;
}
}
if (!hp) break;
}
// cout << "AG" << endl;
cur=bpos[0]; reverse(bpos.begin(), bpos.end());
while (!bits.empty()){
// cout << cur << endl;
for (auto v:A[cur]){
if (bits.count(v)){
cur=v; bpos.push_back(v);
bits.erase(v); break;
}
}
}
if (A[bpos[0]].size()!=cnt[0]){
reverse(bpos.begin(), bpos.end());
}
// cout << "BP: ";
// for (auto ch:bpos) cout << ch << " ";
// cout << endl;
map<ll, ll> mpid;
for (ll i=0; i<10; i++){
mpid[bpos[i]]=i; bits.insert(bpos[i]);
}
bits.insert(r1); bits.insert(r2);
vector<vector<ll>> rA(n);
map<ll, ll> ids;
vector<pair<ll, ll>> e;
for (ll i=0; i<U; i++){
if (bits.count(C[i]) and bits.count(D[i])) continue;
else{
if (bits.count(C[i]) or bits.count(D[i])){
if (bits.count(C[i]) and mpid.count(C[i])){
ids[D[i]]+=(1<<mpid[C[i]]);
}else if(bits.count(D[i]) and mpid.count(D[i])){
ids[C[i]]+=(1<<mpid[D[i]]);
}
}else{
e.push_back({C[i], D[i]});
}
}
}
// cout << "F: " << e.size() << endl;
InitMap(n, e.size());
for (auto [u, v]:e){
// cout << ids[u]-offs << " " << ids[v]-offs << endl;
MakeMap(ids[u]-offs, ids[v]-offs);
}
}
