#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n, m;
vector<vector<pii > > graph;
vector<pii > edges;
vector<bool> done_edge;
vector<bool> vis;
vector<int> order;
const vector<pii > direction = {mp(-1, 0), mp(0, -1), mp(0, 1), mp(1, 0)};
void dfs(int cur) {
vis[cur] = true;
for(pii nei : graph[cur]) {
if(!vis[nei.fi]) {
order.pb(cur);
dfs(nei.fi);
done_edge[nei.se] = true;
}
}
order.pb(cur);
}
void reset() {
n = m = 0;
graph.clear();
edges.clear();
done_edge.clear();
vis.clear();
order.clear();
}
vector<vector<int> > create_map(int N, int M, vector<int> A, vector<int> B) {
reset();
n = N, m = M;
graph.resize(1 + n);
edges.resize(m);
done_edge.assign(m, false);
for(int i = 0; i < m; i++) {
graph[A[i]].pb(mp(B[i], i));
graph[B[i]].pb(mp(A[i], i));
edges[i] = mp(A[i], B[i]);
}
int root = 1;
vis.assign(1 + n, false);
order.pb(root);
dfs(root);
order.pb(root);
vector<vector<int> > pre_ans(2 * n, vector<int> (2 * n, 0));
for(int i = 1; i <= 2 * n; i++) {
pre_ans[i - 1][0] = order[i - 1];
pre_ans[i - 1][1] = order[i];
for(int j = 2; j < 2 * n; j++) {
pre_ans[i - 1][j] = order[i];
}
}
vector<vector<int> > ans(4 * n, vector<int> (4 * n, 0));
vector<queue<pii > > where_to(1 + n);
for(int i = 0; i < 4 * n; i++) {
for(int j = 0; j < 4 * n; j++) {
ans[i][j] = pre_ans[i / 2][j / 2];
}
}
for(int i = 0; i < 2 * n; i++) {
for(int j = 2; j < 2 * n; j++) {
where_to[pre_ans[i][j]].push(mp(2 * i, 2 * j + ((i % 2 == 1) ? 1 : 0)));
}
}
for(int i = 0; i < m; i++) {
if(!done_edge[i]) {
pii pos = where_to[A[i]].front();
where_to[A[i]].pop();
ans[pos.fi][pos.se] = B[i];
for(pii dir : direction) {
pii cur_pos = mp(pos.fi + dir.fi, pos.se + dir.se);
if(cur_pos.fi >= 0 && cur_pos.fi < 4 * n && cur_pos.se >= 0 && cur_pos.se < 4 * n) {
ans[cur_pos.fi][cur_pos.se] = A[i];
}
}
}
}
return ans;
/*vector<vector<int> > ans(2 * N, vector<int> (2 * N, 1));
if (M > 0) {
ans[0][0] = A[0];
ans[0][1] = B[0];
}
return ans;*/
}
