#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int,int>> edge;
int realN = N;
if(!(N & 1))
N++;
int deg[N+12];
memset(deg,0,sizeof(deg));
for(int i=0;i<M;i++) {
edge.push_back({A[i],B[i]});
deg[A[i]] ^= 1;
deg[B[i]] ^= 1;
}
for(int i=0;i<10;i++) {
int cnt = 0;
for(int j=0;j<N;j++)
cnt += !!((1 << i) & (j % realN));
if(cnt & 1) {
for(int j=0;j<N;j++)
if(!!((1<<i)&(j % realN))) {
deg[N+i] ^= 1;
deg[j] ^= 1;
edge.push_back({N+i,j});
}
} else
for(int j=0;j<N;j++)
if(!((1<<i)&(j % realN))) {
deg[N+i] ^= 1;
deg[j] ^= 1;
edge.push_back({N+i,j});
}
}
for(int i=0;i<N;i++)
if(deg[i]) {
edge.push_back({i,N+10});
deg[N+10] ^= 1;
deg[i] ^= 1;
}
for(int i=0;i<12;i++)
cerr << deg[N+i] << " \n"[i==11];
for(int i=0;i<9;i++)
edge.push_back({N+i,N+i+1});
edge.push_back({N+10,N});
edge.push_back({N+9,N+11});
edge.push_back({N+10,N+1});
edge.push_back({N+1,N+3});
edge.push_back({N+3,N+10});
InitG(N+12, edge.size());
for(int i=-1; auto [a, b]: edge)
MakeG(++i, a, b);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
int N = V - 12;
int olddeg[V];
vector<int> adj[V];
memset(olddeg,0,sizeof(olddeg));
for(int i=0;i<U;i++) {
olddeg[C[i]] ^= 1;
olddeg[D[i]] ^= 1;
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
}
int label[V];
memset(label,0,sizeof(label));
int newdeg[V];
memset(newdeg,0,sizeof(newdeg));
for(int i=0;i<V;i++)
if(olddeg[i])
for(auto j: adj[i])
if(olddeg[j])
newdeg[i]++;
for(int i=0;i<V;i++)
if(newdeg[i] == 1) {
label[i] = N + 11;
for(int c=1;c<8;c++) {
for(auto j: adj[i])
if(label[j] == 0 && olddeg[j]) {
i = j;
break;
}
label[i] = N + 10 - c;
}
for(int j=0;j<V;j++)
if(newdeg[j] == 3)
label[j] = N + 10;
else if(newdeg[j] == 4 && label[j] == 0)
label[j] = N + 1;
for(int j=0;j<V;j++)
if(newdeg[j] == 2 && label[j] == 0) {
for(auto k: adj[j])
if(label[k] == N + 10)
label[j] = N;
if(!label[j])
label[j] = N + 2;
}
for(int j=0;j<V;j++)
if(label[j] >= N && label[j] < N + 10) {
int cnt = 0;
for(auto k: adj[j])
if(!olddeg[k])
cnt++;
if(cnt * 2 > N) {
for(int k=0;k<V;k++)
if(!olddeg[k])
label[k] |= (1 << (label[j] - N));
for(auto k: adj[j])
if(!olddeg[k])
label[k] &= ~(1 << (label[j] - N));
} else {
for(auto k: adj[j])
if(!olddeg[k])
label[k] |= (1 << (label[j] - N));
}
}
int fnd = 0;
for(int j=0;j<V;j++)
if(label[j] == N - 1)
fnd = 1;
vector<pair<int,int>> edge;
for(int j=0;j<V;j++)
for(auto k: adj[j])
if(label[j] < label[k] && label[k] < N)
edge.push_back({label[j],label[k]});
InitMap(N - 1 + fnd,edge.size());
for(auto [j, k]: edge)
MakeMap(j, k);
return;
}
}
