#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int m;
int k;
vector<int> haha[100];
vector<int> st(100);
vector<vector<int>> ans(0);
vector<int> tree[100];
vector<int> banana[100];
vector<int> dep(100);
vector<bool> bruh(100);
void reset() {
for(int i = 0; i < 100; i++) {
haha[i].clear();
tree[i].clear();
banana[i].clear();
bruh[i] = true;
dep[i] = -1;
}
ans.clear();
}
void dfs(int a, int d) {
st[a] = 1;
dep[a] = d;
bruh[a] = false;
for(int v: haha[a]) {
if(bruh[v]) {
tree[a].push_back(v);
dfs(v,d+1);
st[a]+=st[v];
}
else if(dep[v] > dep[a]) {
banana[a].push_back(v);
}
}
}
void no(int i, int y, int c) {
for(int j = y; j < k; j++) {
ans[j][i] = c;
}
}
void dude(int x, int y, int a, int w, int p) {
if(st[a] == 1) {
for(int i = y; i < k; i++) {
for(int j = x; j < x+w; j++) {
ans[i][j] = a;
}
}
return;
}
for(int i = 0; i < 2; i++) {
for(int j = x; j < x+w; j++) {
ans[y+i][j] = a;
}
}
no(x,y,a);
int z = x+1;
for(int v: tree[a]) {
dude(z,y+2,v,st[v]*2-1,1-p);
z+=st[v]*2;
no(z-1,y,a);
}
int c = x+1;
if(c%2 != p%2) {
c++;
}
int q = 0;
for(int i = c; i < x+w-1; i+=2) {
if(q < banana[a].size()) {
ans[y+1][i] = banana[a][q];
ans[y+2][i] = a;
q++;
}
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
reset();
n = N;
m = M;
for(int i = 0; i < m; i++) {
haha[A[i]].push_back(B[i]);
haha[B[i]].push_back(A[i]);
}
k = 2*n-1;
for(int i = 0; i < k; i++) {
ans.push_back(vector<int> (k));
}
dfs(1,0);
dude(0,0,1,k,0);
return ans;
}
