#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][2*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++;
}
for (int i=0; i<width; i++) {
for (int j=0; j<width; j++) {
ans[i][j]++;
}
}
tour.clear();
return ans;
}
