#include "worldmap.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
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
void y_comb_demo() {
cout << y_combinator([](auto gcd, int a, int b) -> int {
return b == 0 ? a : gcd(b, a % b);
})(20, 30)
<< "\n";
}
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));
vector<vector<int>> adj(N + 1);
vector<int> vis(N + 1);
for (int i = 0; i < M; ++i) {
adj.at(A.at(i)).push_back(B.at(i));
adj.at(B.at(i)).push_back(A.at(i));
}
auto fill_diag = [&](int d, int v) {
for (int x = 0; x < 2*N; x++) {
int y = d - x;
if (0 <= y && y < 2 * N) ans.at(x).at(y) = v;
}
};
int glob_diag = 0;
int cnt = 0;
auto dfs = y_combinator([&](auto self, int v) -> void {
vis.at(v) = ++cnt;
int diag = glob_diag + 1;
glob_diag += 3;
fill_diag(diag - 1, v);
fill_diag(diag, v);
fill_diag(diag + 1, v);
int x = max(0, diag - 2 * N + 1);
for (int w : adj.at(v)) {
if (!vis.at(w)) {
self(w);
fill_diag(glob_diag, v);
++glob_diag;
} else if (vis.at(w) < vis.at(v)) {
assert(0 <= diag - x && diag - x < 2 * N);
ans.at(x).at(diag - x) = w;
++x;
}
}
});
dfs(1);
while (glob_diag < 4 * N) {
fill_diag(glob_diag, 1);
++glob_diag;
}
assert(cnt == N);
return ans;
}
