#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
void prv(vector<int> &v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
vector<vector<int>> adjlist;
int n,m;
vector<int> visited;
vector<int> tour;
void dfs(int node) {
tour.push_back(node);
visited[node] = 1;
for (int j:adjlist[node]) {
if (!visited[j]) {
dfs(j);
tour.push_back(node);
}
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
n=N; m=M;
int width = 4*n;
vector<vector<int>> ans(width, vector<int>(width, -1));
visited=vector<int>(n,0);
adjlist=vector<vector<int>>(n);
for (int i=0; i<m; i++) {
adjlist[A[i]-1].push_back(B[i]-1);
adjlist[B[i]-1].push_back(A[i]-1);
}
dfs(0);
//cout << "TOURSIZE" <<" " << tour.size() << endl;
//prv(tour);
int rowpointer = 0;
vector<int> seen(n,0);
for (int col:tour) {
if (!seen[col]) {
for (int i=0; i<width; i++) {
ans[rowpointer][i] = col;
}
rowpointer++;
for (int i=0; i<width; i++) {
ans[rowpointer][i] = col;
}
for (int i=0; i<adjlist[col].size(); i++) {
assert(2*i<width);
//cout << tour.size() <<" " << i <<" " << col <<" " << rowpointer << " " << width << " " << n <<" " << endl;
assert(rowpointer<width);
ans[rowpointer][i] = adjlist[col][i];
}
rowpointer++;
for (int i=0; i<width; i++) {
ans[rowpointer][i] = col;
}
rowpointer++;
}
else {
//seen before so just do 1 line
for (int i=0; i<width; i++) {
ans[rowpointer][i] = col;
}
rowpointer++;
}
seen[col] = 1;
}
while (rowpointer<width) {
//cout << rowpointer <<" " << tour.back() <<" " << ans.size() << endl;
for (int i=0; i<width; i++) {
ans[rowpointer][i] = tour.back();
}
rowpointer++;
}
vector<vector<int>> finalans(3*n, vector<int>(3*n,-1));
for (int i=0; i<4*n; i++) {
//the diagonal with sums i+n
vector<int> cords;
for (int x=0; x<3*n; x++) {
int y = i+n-x;
if (0<=y && y<3*n) {
cords.push_back(x);
}
}
for (int j=0; j<cords.size(); j++) {
finalans[i+n-cords[j]][cords[j]] = ans[i][j];
}
}
for (int i=0; i<n*3; i++) {
for (int j=0; j<3*n; j++) {
if (finalans[i][j]==-1) {
if (i>0 && finalans[i-1][j]!=-1) finalans[i][j] = finalans[i-1][j];
if (j>0 && finalans[i][j-1]!=-1) finalans[i][j] = finalans[i][j-1];
}
}
}
for (int i=n*3-1; i>=0; i--) {
for (int j=3*n-1; j>=0; j--) {
if (finalans[i][j]==-1) {
if (i<3*n-1 && finalans[i+1][j]!=-1) finalans[i][j] = finalans[i+1][j];
if (j<3*n-1 && finalans[i][j+1]!=-1) finalans[i][j] = finalans[i][j+1];
}
}
}
for (int i=0; i<3*n; i++) {
for (int j=0; j<3*n; j++) {
finalans[i][j]++;
}
}
tour.clear();
return finalans;
}
