#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
v<int> euler;
v<bool> vis;
v<v<int>> adj;
v<int> par;
v<int> h;
void dfs(int n, int p=-1, int d=0) {
//cout << "DFS: " << n << endl;
vis[n] = true;
par[n] = p;
h[n] = d;
euler.push_back(n);
for (auto x : adj[n]) {
if (!vis[x]) {
dfs(x, n, d+1);
euler.push_back(n);
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
//cout << euler.size() << endl; for (auto x : euler) cout << x << " "; cout << endl;
if (M == 0) {
return {{1}};
}
adj.resize(N);
vis.assign(N, false);
v<v<int>> grid(N, v<int>(N, 0));
par.assign(N, -1);
h.assign(N, 0);
rep(i, 0, M) {
int a = A[i];
int b = B[i];
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
grid[a][b] = 1;
grid[b][a] = 1;
}
dfs(0);
int n = 2*N;
v<v<int>> f(N, v<int>(n));
rep(i, 0, N) {
f[i] = v<int>(n, i+1);
int padre = par[i];
if (padre == -1) continue;
for (int j = n-h[i]*2; j < n-1; j += 2) {
if (padre == -1) continue;
f[i][j] = padre+1;
f[i][j+1] = padre+1;
padre = par[padre];
}
}
rep(i, 0, N) {
for (int j=0;j<n-1; j+=2) {
int a = f[i][j]-1;
if (a == par[i]) continue;
if (par[a] == -1) {
if (grid[i][a]) {
f[i][j+1] = i+1;
}
}
else {
if (grid[i][a]) {
if (grid[i][par[a]]) {
f[i][j+1] = i+1;
}
else {
f[i][j+1] = i+1;
f[i][j+2] = a+1;
j += 2;
}
}
}
}
}
v<v<int>> ans(2*N, v<int>(2*N, 1));
rep(i, 0, (int)euler.size()) {
ans[i] = f[euler[i]];
}
euler.clear();
adj.clear();
grid.clear();
h.clear();
par.clear();
vis.clear();
return ans;
}
