// High above the clouds there is a rainbow...
#include<bits/stdc++.h>
#include "Alicelib.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=1111,lg=10;
static vector<pii>v;
void Alice(int n,int m,int a[],int b[]){
for(int i=0;i<n;i++){
for(int j=0;j<lg;j++){
if(bit(i+1,j)) v.PB({i,j+n});
}
}
for(int i=0;i<n+lg;i++){
v.PB({n+lg,i});
}
for(int i=n;i<n+lg;i++){
v.PB({n+lg+1,i});
}
for(int i=n;i<n+lg-1;i++){
v.PB({i,i+1});
}
InitG(n+lg+2,m+sz(v));
// cout<<n+lg+2<<" "<<m+sz(v)<<endl;
for(int i=0;i<m;i++){
// cout<<a[i]<<" "<<b[i]<<endl;
MakeG(i,a[i],b[i]);
}
for(int i=0;i<sz(v);i++){
// cout<<v[i].F<<" "<<v[i].S<<endl;
MakeG(i+m,v[i].F,v[i].S);
}
}
/*
int a[maxn],b[maxn];
int main(){
int n,m;cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a[i]>>b[i];
}
Alice(n,m,a,b);
}
*/
// High above the clouds there is a rainbow...
#include<bits/stdc++.h>
#include "Boblib.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=1111,lg=10;
static bool bad[maxn];
static int lab[maxn];
static vector<int>v[maxn];
static vector<pii>ans;
static int w2;
static void solve(int u,int prev=-1,int bt=0){
int nxt=-1;
for(int y:v[u]){
if(y==w2) continue;
if(y==prev) continue;
if(bad[y])
lab[y]+= (1<<bt);
else
nxt=y;
}
if(nxt!=-1) solve(nxt,u,bt+1);
}
void Bob(int n,int m,int a[],int b[]){
for(int i=0;i<m;i++)
v[a[i]].PB(b[i]), v[b[i]].PB(a[i]);
int w=0;
for(int i=0;i<n;i++){
if(sz(v[i])>sz(v[w])) w=i;
}
bad[w]=1;
for(int y:v[w]){
bad[y]=1;
}
w2=-1;
for(int i=0;i<n;i++){
if(!bad[i]) w2=i;
}
bad[w2]=1;
for(int y:v[w2]){
bad[y]=0;
}
int A=-1;
for(int i=0;i<n;i++){
if(bad[i]) continue;
int C=0;
for(int y:v[i])
C+= !bad[y];
if(C==1){
if(A==-1) A=i;
else if(sz(v[A]) < sz(v[i])) A=i;
}
}
solve(A);
lab[w]=0;
int N=0,M=0;
for(int i=0;i<m;i++){
if(lab[a[i]]!=0 && lab[b[i]]!=0)
ans.PB( { lab[a[i]]-1, lab[b[i]]-1 } ),M++;
}
for(int i=0;i<n;i++){
if(lab[i]!=0)
N++;
}
InitMap(N,M);
for(pii p:ans){
MakeMap(p.F,p.S);
}
}
/*
int a[maxn],b[maxn];
int main(){
int n,m;cin>>n>>m;
for(int i=0;i<m;i++)
cin>>a[i]>>b[i];
Bob(n,m,a,b);
}
*/
