#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
const int MAXN = 42;
vector<vector<int>> ans;
set<int> tr[MAXN];
bool odw[MAXN];
int ile_pod[MAXN];
bool odw2[MAXN];
int n, m;
void dfs2(int v) {
ile_pod[v] = 0;
odw2[v] = true;
vector<int> us;
set<int> wcz;
for (auto syn: tr[v]) {
if (odw2[syn]) {
us.pb(syn);
}
}
for (auto syn: tr[v]) {
if (odw2[syn]) continue;
dfs2(syn);
ile_pod[v] += ile_pod[syn] + 1;
}
for (auto x: us) {
tr[v].erase(x);
}
}
void dfs(int v, int c, int it, int l, int r) {
// cout << "XD" << endl;
odw[v] = true;
for (int y = l + c; y <= r; y += 2) {
ans[it][y] = v;
}
int d = c ^ 1;
for (int y = l + d; y <= r; y += 2) {
if ((it - 1) >= 0) {
ans[it - 1][y] = v;
}
if ((it + 1) < 2 * n) {
ans[it + 1][y] = v;
}
}
vector<int> syno;
for (auto x: tr[v]) {
syno.pb(x);
cout << "x = " << x << '\n';
}
int sz = syno.size();
int iter = 0;
for (int y = l + d; y <= r; y += 2) {
if (iter < sz) {
ans[it][y] = syno[iter];
}
else {
ans[it][y] = v;
}
iter++;
}
vector<pii> vec;
int l2 = l;
for (auto syn: tr[v]) {
if (odw[syn]) continue;
for (int x = it + 1; x < 2 * n; x++) {
ans[x][l2] = v;
}
l2++;
int e = c;
if (ans[it][l2] == v) {
e ^= 1;
}
dfs(syn, e, it + 2, l2, l2 + 2 * ile_pod[v]);
l2 = l2 + 2 * ile_pod[v] + 1;
}
for (int x = it + 1; x < 2 * n; x++) {
ans[x][l2] = v;
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
n = N;
m = M;
rep(i, 2 * n) {
ans.pb({});
rep(j, 2 * n) {
ans[i].pb(-1);
}
}
rep(i, m) {
int a = A[i];
int b = B[i];
tr[a].insert(b);
tr[b].insert(a);
}
// cout << "FR" << endl;
dfs2(1);
dfs(1, 0, 0, 0, 2 * n - 1);
rep(i, 2 * n) {
rep(j, 2 * n) {
if (ans[i][j] == -1) {
int kt = -1;
if (i > 0 && ans[i - 1][j] >= 0) {
kt = ans[i - 1][j];
}
else if (j > 0) {
kt = ans[i][j - 1];
}
ans[i][j] = kt;
}
}
}
return ans;
}
