#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 42;
vector<int> adj[mxN], waiting[mxN];
vector<int> ord;
int parent[mxN], leaf[mxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int find(int u){
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
bool unite(int u, int v){
u = find(u), v = find(v);
if(u == v) return 0;
parent[u] = v;
return 1;
}
void dfs(int u = 1, int par = 0){
for(auto it : adj[u]){
if(it ^ par) {
ord.push_back(u);
dfs(it, u);
}
}
if(u != 1) ord.push_back(u);
}
void reset(int N){
ord.clear();
for(int i = 1; i <= N; ++i){
adj[i].clear();
waiting[i].clear();
parent[i] = i;
leaf[i] = 0;
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
reset(N);
vector<vector<bool>> mat(N + 5, vector<bool> (N + 5, 0));
if(N == 1){
return {{1}};
}
for(int i = 0; i < M; ++i){
if(unite(A[i], B[i])){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
waiting[A[i]].push_back(B[i]);
waiting[B[i]].push_back(A[i]);
mat[A[i]][B[i]] = 1;
mat[B[i]][A[i]] = 1;
mat[A[i]][A[i]] = 1;
mat[B[i]][B[i]] = 1;
}
dfs(1, 0);
vector<vector<int>> ans;
int mx = 0;
for(int i = 0; i < ord.size(); ++i){
if(leaf[ord[i]]) {
leaf[ord[i]] = 0;
continue;
}
vector<int> top_layer = {ord[i]};
vector<int> mid_layer;
for(auto it : waiting[ord[i]]){
mid_layer.push_back(it);
mid_layer.push_back(ord[i]);
}
mx = max(mx, (int) mid_layer.size());
ans.push_back(top_layer);
if(mid_layer.size()) ans.push_back(mid_layer);
ans.push_back(top_layer);
}
while(mx > ans.size()) ans.push_back(ans.back());
for(int i = 0; i < (int) ans.size(); ++i){
int x = ans[i][0];
if(ans[i].size() > 1) x = ans[i][1];
while((int) ans.size() > (int) ans[i].size()) {
ans[i].push_back(x);
}
assert(ans.size() == ans[i].size());
}
assert(ans.size() <= 240);
reset(N);
for(int i = 0; i < (int) ans.size(); ++i){
assert(ans.size() == ans[i].size());
for(int j = 0; j < (int) ans[i].size(); ++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) < (int) ans.size()){
assert(ans[i][j] <= N && ans[i][j] >= 1);
assert(ans[ni][nj] <= N && ans[ni][nj] >= 1);
if(ans[i][j] != ans[ni][nj]) {
//assert();
//cout << i << " " << j << "\n";
if(!mat[ans[i][j]][ans[ni][nj]]) cout << i << " " << j << "\n";
}
}
}
}
}
return ans;
}
