#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
/*3*n*/
int n, ad[45][45], a[2005][2005];
bool visited[45];
void dfs(int u, int &r, int &c)
{
visited[u] = 1;
vector<int> child;
for(int v = 1; v <= n; v++) if(ad[u][v] == 1 && visited[v] == 0) child.push_back(v);
if(child.size() == 0){
a[r][c] = u; c++; return;
}
int befr = r, rec = c;
//Create a boarder
for(int i : child){
a[r][c++] = u; a[r][c++] = u;
}
a[r][c++] = u; r++; c = rec;
for(int i : child){
a[r][c++] = u; a[r][c++] = i;
}
a[r][c++] = u; r++; c = rec;
for(int i : child){
a[r][c++] = u; a[r][c++] = u;
}
a[r][c++] = u; r++; c = rec;
int maxr = r, rer = r;
for(int v : child) if(visited[v] == 0){
c++; dfs(v, r, c);
maxr = max(maxr, r); r = rer;
}
for(int i = befr; i <= rer; i++){
for(int j = rec; j <= c; j++) if(a[i][j] == 0) a[i][j] = u;
}
for(int i = rer; i <= maxr; i++){
for(int j = rec; j <= c; j++) if(a[i][j] == 0) a[i][j] = a[i-1][j]; //Extend down
}
r = maxr; c++;
}
vector<vector<int>> create_map(int nn, int m, vector<int> A, vector<int> B)
{
n = nn;
memset(ad, 0, sizeof(ad));
for(int i = 0; i < m; i++){
int u = A[i], v = B[i];
ad[u][v] = ad[v][u] = 1;
}
memset(visited, 0, sizeof(visited));
memset(a, 0, sizeof(a));
int r = 0, c = 0;
dfs(1, r, c);
vector<vector<int>> ans;
for(int i = 1; i <= r; i++){
vector<int> cur;
for(int j = 0; j < c; j++) cur.push_back(a[i][j]);
ans.push_back(cur);
}
while(ans.size() < ans[0].size()) ans.push_back(ans.back());
while(ans.size() > ans[0].size()){
for(int i = 0; i < ans.size(); i++) ans[i].push_back(ans[i].back());
}
return ans;
}
