#include <bits/stdc++.h> using namespace std; #define all(a) (a).begin(), (a).end() #define ll long long #define ld long double #define ui __int128_t #define pb push_back template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; } template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); static inline uint64_t splitmix64(uint64_t &x) { x += 0x9e3779b97f4a7c15ULL; uint64_t z = x; z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL; z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL; return z ^ (z >> 31); } /********* DEBUG *********/ template<typename T> struct is_vector : false_type {}; template<typename T, typename A> struct is_vector<vector<T, A>> : true_type {}; template<typename T> void print_one(const T& x) { if constexpr (is_vector<T>::value) { for (size_t i = 0; i < x.size(); i++) { cout << x[i]; if (i + 1 < x.size()) cout << ' '; } } else { cout << x; } } template<typename... Args> void out(const Args&... args) { bool first = true; auto print_arg = [&](const auto& v) { if (!first) cout << ' '; first = false; print_one(v); }; (print_arg(args), ...); cout << "\n"; } /********* DEBUG *********/ #define fi first #define se second const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const ll inf = 1e18; const ll RUNS = 100000; const ll LOG = 31; const ll MAXN = 2e5; #include "worldmap.h" std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { vector<vector<ll>> adj(N), back(N); for (int i = 0; i < M; i++) { A[i]--; B[i]--; adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]); } vector<ll> euler, dep(N, -1), idx(N); dep[0] = 0; auto dfs = [&](auto &&dfs, ll u, ll p) -> void { euler.pb(u); idx[u] = euler.size(); euler.pb(u); euler.pb(u); for (auto &v : adj[u]) { if (v == p) continue; if (dep[v] == -1) { dep[v] = dep[u] + 1; dfs(dfs, v, u); } else if (dep[v] < dep[u]) { back[u].pb(v); } } }; dfs(dfs, 0, 0); assert(euler.size() == 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] = euler[i + j]; } } for (int i = 0; i < N; i++) { ll r = min(idx[i], 2LL*N - 1); ll c = max(0LL, idx[i] - 2*N + 1); for (auto &v : back[i]) { ans[r][c] = v; r--; c++; } } return ans; }