//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "Alicelib.h"
const int maxn = 2020;
int id[maxn];
void Alice( int N, int M, int A[], int B[] ){
int cur = 0,tot=1,ecnt=0;
rep(i,1,N+1) {
while (tot == (1<<cur)) cur++,tot++;
id[i] = tot++;
ecnt += __builtin_popcount(id[i]);
}
InitG(N+12,M+9+10+1+ecnt);
rep(i,0,M) {
MakeG(i,A[i],B[i]);
}
rep(i,0,9) MakeG(i+M,N+i,N+i+1);
rep(i,0,10) MakeG(i+M+9,N+10,N+i);
MakeG(M+9+10,N+10,N+11);
int tmp = M+9+10+1;
rep(i,1,N+1) {
rep(j,0,10) if ((id[i]>>j)&1) MakeG(tmp++,i-1,N+j);
}
}
//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "Boblib.h"
int deg[2020];
vector <int> edge[2020];
vector <pii> ans;
int mp[2020];
int p[2020];
bool mark[2020];
int val[2020];
int con[2020][2020];
void Bob( int V, int U, int C[], int D[] ){
rep(i,0,U) {
deg[C[i]]++;
deg[D[i]]++;
edge[C[i]].pb(D[i]);
edge[D[i]].pb(C[i]);
con[C[i]][D[i]] = con[D[i]][C[i]] = 1;
}
int hi = -1;
rep(i,0,V) if (deg[i]==1) hi = i;
assert(hi!=-1);
int hii = edge[hi][0];
mark[hii] = mark[hi] = 1;
vector <int> node;
int st=-1;
for (int v:edge[hii]) {
if (v==hi) continue;
mark[v] = 1;
int cnt = 0;
for (int to:edge[v]) {
if (con[to][hii]) cnt++;
if (cnt==2) break;
}
assert (cnt==2 or cnt==1);
if (cnt==1 and (st==-1 or deg[v]>deg[st])) st = v;
}
assert(st!=-1);
int lst = -1;
node.pb(st);p[st] = 0;
// debug(hi);debug(hii);
rep(i,0,9) {
int to = -1;
for (int v:edge[st]) if (v!=lst and v!=hii and mark[v]) to = v;
p[to] = SZ(node);
node.pb(to);
mark[to] =1;
lst = st, st = to;
// debug(st);
}
rep(i,0,U) {
if (mark[C[i]]==0 and mark[D[i]]==0) ans.pb({C[i],D[i]});
else if (mark[C[i]]==0 and mark[D[i]]==1) val[C[i]] += (1<<p[D[i]]);
else if (mark[D[i]]==0 and mark[C[i]]==1) val[D[i]] += (1<<p[C[i]]);
}
rep(i,0,SZ(ans)) ans[i].fi = val[ans[i].fi],ans[i].se = val[ans[i].se];
int cur = 0,tot=1;
rep(i,0,V-12) {
while (tot == (1<<cur)) cur++,tot++;
mp[tot++] = i;
}
InitMap(V-12,SZ(ans));
rep(i,0,SZ(ans)) MakeMap(mp[ans[i].fi],mp[ans[i].se]);
}
