#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 20;
static vector<int> adj[MAXN];
void add(int a, int b){
adj[a].push_back(b);
adj[b].push_back(a);
}
void Alice(int n, int m, int a[], int b[]){
for(int i=0; i<m; i++) add(a[i], b[i]);
for(int i=0; i<n; i++){
for(int j=0; j<10; j++){
if(i & (1 << j)){
add(i, n + j);
}
}
add(i, n + 10);
}
for(int i=0; i<10; i++){
add(n + i, n + 10);
add(n + i, n + 11);
if(i < 9) add(n + i, n + i + 1);
}
int v = n + 12;
int u = 0;
for(int i=0; i<v; i++) u += (int) adj[i].size();
u /= 2;
InitG(v, u);
int cnt = 0;
for(int i=0; i<v; i++){
for(auto j : adj[i]){
if(i < j) MakeG(cnt++, i, j);
}
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 20;
int marc[MAXN], id[MAXN];
static vector<int> adj[MAXN];
void Bob(int v, int u, int c[], int d[]){
for(int i=0; i<u; i++){
adj[c[i]].push_back(d[i]);
adj[d[i]].push_back(c[i]);
}
int x = 0;
for(int i=0; i<v; i++) if(adj[i].size() > adj[x].size()) x = i;
marc[x] = 1;
for(auto i : adj[x]) marc[i] ++;
int y = 0;
for(int i=0; i<v; i++){
if(!marc[i]) y = i;
marc[i] = 0;
}
for(auto i : adj[y]) marc[i] = 1;
int first_bit = -1;
for(auto i : adj[y]){
int cnt = 0;
for(auto j : adj[i]) cnt += marc[j];
if(cnt == 1){
if(first_bit == -1 || (int) adj[i].size() > (int) adj[first_bit].size()){
first_bit = i;
}
}
}
vector<int> ord;
int cur = first_bit;
while((int) ord.size() < 10){
ord.push_back(cur);
marc[cur] = 0;
id[cur] = 1e9;
for(auto i : adj[cur]) if(marc[i]) cur = i;
}
for(int i=0; i<10; i++) for(auto j : adj[ord[i]]) id[j] += (1 << i);
int n = v - 12;
vector<pair<int, int>> edges;
for(int i=0; i<v; i++){
if(id[i] >= n) continue;
for(auto j : adj[i]){
if(id[j] < id[i]){
edges.push_back({id[j], id[i]});
}
}
}
for(auto [a, b] : edges) cout << a << " " << b << endl;
InitMap(n, (int) edges.size());
for(auto [a, b] : edges) MakeMap(a, b);
}
