#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
namespace std {
template <class Fun> class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args> decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
int n, t=0, dc=0;
vector<int> vis;
vector<vector<int>> ans, adj;
void fill(int d, int v) {
for (int x = 0; x < 2*n; x++) {
if (0<=d-x && d-x<2*n) ans[x][d-x]=v;
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
n=N;
ans.assign(2*n, vector<int>(2*n, 1));
adj.assign(n+1, vector<int>());
vis.assign(n+1, 0);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
int glob_diag = 0;
int cnt = 0;
auto dfs = y_combinator([&](auto self, int v) -> void {
vis[v]=++cnt;
int diag=dc+1;
dc+=3;
fill(diag-1, v);
fill(diag, v);
fill(diag+1, v);
int x = max(0, diag-2*n+1);
for (int w : adj.at(v)) {
if (!vis.at(w)) {
self(w);
fill(dc++, v);
} else if (vis[w] < vis[v]) {
ans.at(x).at(diag-x) = w;
++x;
}
}
});
dfs(1);
return ans;
}
