#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 42;
vector<pair<int, int>> ord;
set<int> adj[mxN];
bool vis[mxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void dfs(int u, int par){
if(par > 0) {
ord.push_back({u, par});
if(adj[u].find(par) != adj[u].end()){
adj[u].erase(par);
}
if(adj[par].find(u) != adj[par].end()){
adj[par].erase(u);
}
}
vis[u] = 1;
for(auto it : adj[u]){
if(it ^ par){
if(!vis[it]){
dfs(it, u);
}
}
}
if(par > 0) ord.push_back({par, u});
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
if(N == 1){
return {{1}};
}
vector<vector<int>> mat(N + 1, vector<int>(N + 1, 0));
for(int i = 1; i <= N; ++i) vis[i] = 0;
for(int i = 0; i < M; ++i){
adj[A[i]].insert(B[i]);
adj[B[i]].insert(A[i]);
mat[A[i]][B[i]] = 1;
mat[B[i]][A[i]] = 1;
}
dfs(1, 0);
vector<vector<int>> demo(max(1, (int) ord.size()), vector<int>(max(1, (int) ord.size()), 1));
vector<vector<int>> ans;
for(int i = 0; i < ord.size(); ++i){
demo[i][0] = ord[i].first;
demo[i][1] = ord[i].second;
for(int j = 2; j < ord.size(); ++j) demo[i][j] = demo[i][0];
}
for(int i = 0; i < (int) demo.size(); ++i){
ans.push_back(demo[i]);
vector<int> layer((int) demo.size(), demo[i][0]);
for(int j = 0; j < min((int) demo.size(), (int) adj[demo[i][0]].size()); ++j){
if(j == 1) continue;
layer[j] = *adj[demo[i][0]].begin();
adj[demo[i][0]].erase(layer[j]);
}
ans.push_back(layer);
ans.push_back(demo[i]);
}
for(int i = 1; i <= N; ++i) adj[i].clear(), vis[i] = 0;
ord.clear();
for(int i = 0; i < ans.size(); ++i){
while(ans[i].size() < ans.size()){
ans[i].push_back(ans[i][0]);
}
}
for(int i = 0 ; i < ans.size(); ++i){
assert(ans.size() == ans[i].size());
}
int r = ans.size();
for(int i = 0; i < r; ++i){
for(int j = 0; j < r; ++j){
for(int k = 0; k < 4; ++k){
int ni = i + dx[k], nj = j + dy[k];
if(min(ni, nj) >= 0 && max(ni, nj) < k){
if(ans[i][j] != ans[ni][nj]){
assert(mat[ans[i][j]][ans[ni][nj]]);
}
}
}
}
}
assert(ans.size() <= 240);
return ans;
}
