#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long
constexpr int maxN=2e5+5;
//#define LOCAL
#ifdef LOCAL
void InitG( int V, int U ){
}
void MakeG( int pos, int C, int D ){
}
#else
#include"Alicelib.h"
#endif
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int,int>> edges;
for(int i = 0;i<M;i++)edges.emplace_back(A[i],B[i]);
for(int i = 0;i<10;i++){
if(i)edges.emplace_back(N+i,N+i+1);
edges.emplace_back(N,N+i+1);
for(int j = 0;j<N;j++)if(j>>i&1)edges.emplace_back(N+i+1,j);
}
for(int i = 0;i<N+11;i++)if(i!=N)edges.emplace_back(N+11,i);
InitG(N+12,edges.size());
int cnt = 0;
for(auto [a,b]:edges)MakeG(cnt++,a,b);
}
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long
constexpr int maxN=2e5+5;
//#define LOCAL
#ifdef LOCAL
void InitMap( int N, int M ){
}
void MakeMap( int A, int B ){
}
#else
#include"Boblib.h"
#endif
void Bob( int V, int U, int C[], int D[] ){
vector<int> deg(V);
vector adj(V,vector(V,0));
for(int i = 0;i<U;i++)deg[C[i]]++,deg[D[i]]++,adj[C[i]][D[i]]=adj[D[i]][C[i]]=1;
int idx = max_element(all(deg))-deg.begin(),idx2 = 0;
vector<int> bits,dead(V);
dead[idx] = 1;
for(int i = 0;i<V;i++)if(i!=idx&&!adj[idx][i])idx2=i;
dead[idx2] = 1;
for(int i = 0;i<V;i++)if(adj[idx2][i])bits.emplace_back(i),dead[i]=1;
vector<int> neighbor[10];
for(int i = 0;i<10;i++){
int b1 = bits[i];
for(int j = 0;j<10;j++){
int b2 = bits[j];
if(b2!=b1&&adj[b1][b2])neighbor[i].emplace_back(j);
}
}
int ends[2]{};
for(int i = 0;i<10;i++)if(neighbor[i].size()==1){
if(!ends[0])ends[0]=i;
else {
ends[1] = i;
if(deg[bits[ends[0]]]<deg[bits[ends[1]]])swap(ends[0],ends[1]);
}
}
vector<int> rlid(V),vis(10);
for(int pos = ends[0],bit = 0;;bit++){
vis[pos] = 1;
for(int i = 0;i<V;i++)if(!dead[i]&&adj[bits[pos]][i]){
rlid[i]|=1<<bit;
}
if(pos==ends[1])break;
if(vis[neighbor[pos][0]])pos = neighbor[pos][1];
else pos = neighbor[pos][0];
}
vector<pair<int,int>> edges;
for(int i = 0;i<U;i++){
if(!dead[C[i]]&&!dead[D[i]])edges.emplace_back(rlid[C[i]],rlid[D[i]]);
}
InitMap(V-12,edges.size());
for(auto [a,b]:edges)MakeMap(a,b);
}
