#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> v[50];
int n, k;
int f[50];
void dfs(int x, int pa, vector<vector<int>> &ans) {
// cout << "[x]: " << x << endl;
f[x] = 1;
for (int i = max(0, k - 2 * n + 1); i <= min(k, 2 * n - 1); ++i) {
ans[i][k - i] = x;
}
k++;
for (int y : v[x]) {
if(f[y]) continue;
dfs(y, x, ans);
// cout << x << "AAA" << endl;
}
int e = max(0, k - 2 * n + 1);
if(x != 0) {
for (int y : v[x]) {
if(f[y] == 2) continue;
assert(f[y] == 1);
ans[e][k - e] = y;
e++;
}
while (e <= min(k, 2 * n - 1)) {
ans[e][k - e] = x;
e++;
}
k++;
for (int i = max(0, k - 2 * n + 1); i <= min(k, 2 * n - 1); ++i) {
ans[i][k - i] = x;
}
k++;
for (int i = max(0, k - 2 * n + 1); i <= min(k, 2 * n - 1); ++i) {
ans[i][k - i] = pa;
}
k++;
f[x] = 2;
}
// cout << "[x]: " << x << endl;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> ans(2 * N, vector<int>(2 * N, 0));
n = N;
for (int i = 0; i < 50; ++i) {
v[i].clear();
f[i] = 0;
}
for (int i = 0; i < M; ++i) {
v[A[i] - 1].push_back(B[i] - 1);
v[B[i] - 1].push_back(A[i] - 1);
}
dfs(0, 0, ans);
// assert(k == 4 * N - 2);
for (int i = 0; i < 2 * N; ++i) {
for (int j = 0; j < 2 * N; ++j) {
ans[i][j]++;
// cout << ans[i][j] << " ";
}
// cout << endl;
}
k = 0;
return ans;
}
