#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<pair<int, int>>> adj(N+1);
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], i);
adj[B[i]].emplace_back(A[i], i);
}
vector<int> rizzler, loc(N+1, -1), dep(N+1);
vector<bool> vis(N+1);
vector<set<int>> back(N+1);
auto dfs = [&](auto &&dfs, int u, int p) -> void {
rizzler.push_back(u);
loc[u] = rizzler.size();
rizzler.push_back(u);
rizzler.push_back(u);
for (auto &[v, id] : adj[u]) {
if (v == p) continue;
if (vis[v]) {
if (dep[u] > dep[v]) back[u].insert(v);
} else {
vis[v] = true;
dep[v] = dep[u] + 1;
dfs(dfs, v, u);
rizzler.push_back(u);
}
}
};
vis[1] = true;
dfs(dfs, 1, 0);
cerr << N sp rizzler.size() << endl;
for (auto &x : rizzler) cerr << x << " ";
cerr << endl;
int K = rizzler.size();
assert(K == 4*N-1);
vector<vector<int>> ans(2*N, vector<int>(2*N));
for (int i = 0; i < 2*N; i++) {
for (int j = 0; j < 2*N; j++) {
ans[i][j] = rizzler[i+j];
}
}
for (int u = 1; u <= N; u++) {
// cerr << u sp loc[u] << endl;
int j = loc[u], k = (j >= 2*N ? j-2*N+1 : 0);
for (auto &v : back[u]) {
if (0 <= k and k < 2*N and 0 <= j-k and j-k < 2*N)
ans[k][j-k] = v;
k++;
}
}
return ans;
}
