#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
static vector<int> grafo[MAXN], vgrafo[1505];
static int marc[1505][1505];
void Alice( int N, int M, int A[], int B[] ){
for(int i = 0; i < M; i++) {
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
int n = 0, m = 0;
n++;
n++;
for(auto u : grafo[0]){
if(u == 1){
vgrafo[0].push_back(1);
vgrafo[1].push_back(0);
m++;
}
}
for(int i = 2; i < N; i++){
int r = n;
int con = n + 1;
n++;
vgrafo[r].push_back(n);
vgrafo[n].push_back(r);
m++;
n++;
vgrafo[con].push_back(n);
vgrafo[n].push_back(con);
m++;
n++;
vgrafo[r].push_back(n);
vgrafo[n].push_back(r);
m++;
vgrafo[con].push_back(n);
vgrafo[n].push_back(con);
m++;
n++;
vgrafo[r].push_back(n);
vgrafo[n].push_back(r);
m++;
vgrafo[con].push_back(n);
vgrafo[n].push_back(con);
m++;
for(auto u : grafo[i]){
if(u == 0){
vgrafo[n].push_back(n-1);
vgrafo[n-1].push_back(n);
m++;
}
}
vector<int> qual;
qual.push_back(r);
for(int j = 1; j <= i; j++){
n++;
vgrafo[qual[j-1]].push_back(n);
vgrafo[n].push_back(qual[j-1]);
m++;
qual.push_back(n);
}
for(auto u : grafo[i]){
if(u == 0 || u > i) continue;
vgrafo[qual[u]].push_back(con);
vgrafo[con].push_back(qual[u]);
m++;
}
vgrafo[qual[i]].push_back(con);
vgrafo[con].push_back(qual[i]);
m++;
n++;
}
if(n == 0){
InitG(1, 0);
return;
}
InitG(n, m);
int it = 0;
for(int i = 0; i <= n; i++){
for(auto u : vgrafo[i]){
if(!marc[i][u]){
MakeG(it, i, u);
it++;
marc[i][u] = 1;
marc[u][i] = 1;
}
}
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
static vector<int> vgrafo[1505];
static vector<pair<int, int> > grafo;
static int marc1[1505][1505], marc2[1505][1505];
static int marc[1505];
int dfs(int x, int p, int h, int con){
int maxh = h;
for(int i = 0; i < vgrafo[x].size(); i++){
int viz = vgrafo[x][i];
if(viz == p || viz == con) continue;
maxh = max(maxh, dfs(viz, x, h + 1, con));
}
return maxh;
}
void Bob( int V, int U, int C[], int D[] ){
if(V == 1){
InitMap(1, 0);
return;
}
bool okk= 0;
if(V == 2){
if(U != 0){
InitMap(2, 1);
MakeMap(1, 0);
}
else{
InitMap(2,0);
}
return;
}
for(int i = 0; i < U; i++ ){
vgrafo[C[i]].push_back(D[i]);
vgrafo[D[i]].push_back(C[i]);
//printf("%d %d\n", C[i], D[i]);
}
int n = 1, m = 0;
for(int i = 0; i < V; i++){
//printf("%d\n", i);
if(vgrafo[i].size() == 1 ){
if(vgrafo[vgrafo[i][0]].size() == 1 &&!okk){
n = max(n, 2);
grafo.push_back(make_pair(1, 0));
m++;
okk = 1;
}
}
if(vgrafo[i].size() != 4) continue;
int esse = 1;
int con;
int vizini, isconec = 0;;
for(auto u : vgrafo[i]){
marc[u] = 1;
if(vgrafo[u].size() > 4) con = u;
}
marc[i] = 1;
for(auto u : vgrafo[i]){
bool ok = 0;
for(auto v : vgrafo[u]){
if(!marc[v]) ok = 1;
}
if(ok && u != con){
vizini = u;
break;
}
}
for(auto u : vgrafo[i]){
if(vizini == u || con == u) continue;
if(vgrafo[u].size() == 3) isconec = 1;
}
esse = dfs(vizini, i, 1, con);
n = max(esse, n);
if(isconec){
grafo.push_back(make_pair(esse, 0));
//printf("GREAL %d %d\n", esse, 0);
m++;
}
if(esse == 1) continue;
if(esse == 0){
printf("ESSERUIM\n");
}
int ult = i;
for(int j = 1; j < esse; j++){
if(vgrafo[vizini].size() > 2){
grafo.push_back(make_pair(esse, j));
//printf("GREAL %d %d\n", esse, 0);
m++;
}
for(auto u : vgrafo[vizini]){
if(vgrafo[u].size() > 1 && u != ult && u != con){
ult = vizini;
vizini = u;
break;
}
}
}
}
//printf("%d\n",m );
InitMap(n + 1, m);
for(int i = 0; i < m; i++){
MakeMap(grafo[i].first, grafo[i].second);
}
}
