#include"bits/stdc++.h"
#include"Alicelib.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };
// void InitG(int V, int U)
// void MakeG(int pos, int C, int D)
void Alice(int N, int M, int A[], int B[]){
vector<pair<int,int>> ret;
rep(i, M) ret.pb({ A[i], B[i] });
rep(i, N){
rep(j, 10){
if((i>>j)&1) ret.pb({i, N+j});
}
}
rep(i, 10) ret.pb({ N+10, N+i });
rep(i, 9) ret.pb({ N+i, N+1+i });
rep(i, N+10){
if(N > 500 && i == N) continue;
if(N <= 500 && i == N+9) continue;
ret.pb({ i, N+11 });
}
InitG(N+12, ret.size());
rep(i, ret.size()) MakeG(i, ret[i].first, ret[i].second);
}
#include"bits/stdc++.h"
#include"Boblib.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };
// void InitMap(int N, int M)
// void MakeMap(int A, int B)
bool isExist(vector<int>& v, int n){
rep(i, v.size()){
if(v[i] == n) return true;
}
return false;
}
void Bob(int V, int U, int C[], int D[]){
if(V == 13){
InitMap(1, 0);
return;
}
vector<int> e[1020];
rep(i, U){
e[C[i]].pb(D[i]);
e[D[i]].pb(C[i]);
//cout << C[i] << " " << D[i] << endl;
}
int N = V-12;
int r, b;
vector<int> t(10, -1);
rep(i, V){
if(e[i].size() == N+9){
r = i;
rep(j, V){
if(j != r && !isExist(e[r], j) && e[j].size() == 10) b = j;
else if(j != r && !isExist(e[r], j)) t[0] = j;
}
int c = 0;
rep(j, 10){
if(isExist(e[t[0]], e[b][j])) c++;
}
if(c == 1 && e[t[0]].size()-2 == N/2) break;
}
}
rep(i, 9){
rep(j, 10){
//cout << e[b][j] << " " << isExist(e[t[i]], e[b][j]) << " " << !isExist(t, e[b][j]) << endl;
if(isExist(e[t[i]], e[b][j]) && !isExist(t, e[b][j])){
t[i+1] = e[b][j];
}
}
}
if(N <= 500) reverse(all(t));
//cout << "rb: " << r << " " << b << endl;
//rep(i, 10) cout << t[i] << " ";
//cout << endl;
vector<int> ans(V, 0);
rep(i, 10){
rep(j, e[t[i]].size()){
ans[e[t[i]][j]] += 1<<i;
}
}
t.pb(r);
t.pb(b);
vector<pair<int, int>> edges;
rep(i, U){
if(isExist(t, C[i]) || isExist(t, D[i])) continue;
edges.pb({ ans[C[i]], ans[D[i]] });
//cout << ans[C[i]] << " " << ans[D[i]] << endl;
}
InitMap(N, edges.size());
rep(i, edges.size()) MakeMap(edges[i].first, edges[i].second);
}
