#include "worldmap.h"
#include <cassert>
#include <cstdio>
#include <iostream>
using namespace std;
void getOrder(vector<int> &order, vector<bool> &vis, int i, vector<vector<int>> edges) {
if (vis[i]) return;
vis[i] = true;
for (int j : edges[i]) {
if (vis[j]) continue;
order.push_back(i);
getOrder(order, vis, j, edges);
}
order.push_back(i);
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> edges(N);
for (int i = 0; i < M; i++) {
edges[A[i] - 1].push_back(B[i] - 1);
edges[B[i] - 1].push_back(A[i] - 1);
}
vector<int> order;
vector<bool> vis(N);
getOrder(order, vis, 0, edges);
for (int i = 0; i < N; i++) vis[i] = false;
vector<vector<int>> ans(4 * N, vector<int>(4 * N, 0));
int cur = 0;
int phase = 0;
for (int i = N - 1; i < 4 * N && cur < order.size(); i++) {
if (vis[order[cur]] && phase == 1) {
cur++;
phase = 0;
i--;
continue;
}
if (phase == 0 || phase == 2) {
int x = 0;
int y = i;
while (y >= 0) {
ans[x][y] = order[cur];
x++;
y--;
}
phase++;
if (phase == 3) {
cur++;
phase = 0;
}
}
else if (phase == 1) {
vis[order[cur]] = true;
int x = 0;
int y = i;
int ind = 0;
while (y >= 0) {
if (ind < edges[order[cur]].size()) {
if (vis[edges[order[cur]][ind]]) {
ind++;
continue;
}
ans[x][y] = edges[order[cur]][ind++];
}
else ans[x][y] = order[cur];
x++;
y--;
}
phase++;
}
}
for (int i = 1; i < 4 * N && cur < order.size(); i++) {
if (vis[order[cur]] && phase == 1) {
cur++;
phase = 0;
i--;
continue;
}
if (phase == 0 || phase == 2) {
int x = i;
int y = 4 * N - 1;
while (x < 4 * N) {
ans[x][y] = order[cur];
x++;
y--;
}
phase++;
if (phase == 3) {
cur++;
phase = 0;
}
}
else if (phase == 1) {
vis[order[cur]] = true;
int x = i;
int y = 4 * N - 1;
int ind = 0;
while (x < 4 * N) {
if (ind < edges[order[cur]].size()) {
if (vis[edges[order[cur]][ind]]) {
ind++;
continue;
}
ans[x][y] = edges[order[cur]][ind++];
}
else ans[x][y] = order[cur];
x++;
y--;
}
phase++;
}
}
for (int i = 0; i < 4 * N; i++) {
for (int j = 0; j < 4 * N; j++) {
ans[i][j]++;
}
}
return ans;
}
