#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
vector<vector<int>> adj;
adj.resize(n+1,vector<int>{});
for(int i = 0; i < m; ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
if(m == 0){
return vector<vector<int>>{vector<int>{1}};
}
//testing
if(true){
vector<int> row;
vector<bool> vis(n+1,false);
auto dfs = [&](int ind, auto &&dfs) -> void {
vis[ind]=true;
for(auto &u : adj[ind]) {
if(vis[u]) continue;
row.emplace_back(ind);
dfs(u,dfs);
}
row.push_back(ind);
};
dfs(1, dfs);
int sz= row.size();
vector<vector<int>> ans(3 *sz, vector<int>(3 * sz, 0));
vector<bool> F(n+1,false); int last= 0;
for(int i = 0; i < sz; ++i) {
int u = row[i];
queue<int> Q;
for(auto &v : adj[u]){
Q.push(v);
}
if(F[u]){
for(int j = 0; j < 3*sz;++j)ans[j][last]=u;
++last;
}else{
int p1 = last;
int p2 = last+1;
int p3 = last+2;
for(int j = 0; j < 3 * sz; ++j){
if(j & 1 or Q.empty()){
ans[j][p1]=ans[j][p2]=ans[j][p3]=u;
}else{
ans[j][p1]=ans[j][p3]=u;
ans[j][p2]=Q.front();
Q.pop();
}
}
}
F[u]=true;
}
return ans;
}
//testing
if(n <= 15) {
vector<int> row;
vector<bool> vis(n+1,false);
auto dfs = [&](int ind, auto &&dfs) -> void {
vis[ind] = true;
for(auto &u : adj[ind]) {
if(vis[u]) continue;
row.emplace_back(ind);
row.emplace_back(u);
}
if(row.back() != ind) row.emplace_back(ind);
for(auto &u : adj[ind]) {
if(vis[u]) continue;
dfs(u, dfs);
row.emplace_back(ind);
}
};
dfs(1,dfs);
int sz = row.size();
vector<vector<int>> ans;
for(int i = 0; i < sz; ++i){
ans.push_back(row);
}
return ans;
}
if(m == n-1) {
vector<int> row;
auto dfs = [&](int ind, int par, auto &&dfs) -> void {
for(auto &u : adj[ind]) {
if(u == par) continue;
row.emplace_back(ind);
dfs(u,ind,dfs);
}
if(ind != 1) row.push_back(ind);
};
dfs(1, -1, dfs);
int sz = row.size();
vector<vector<int>> ans;
for(int i = 0; i < sz; ++i){
ans.push_back(row);
}
return ans;
}
vector<vector<int>> ans(2*n,vector<int>(2*n,1));
for(int i = 0; i < 2 * n; ++i) {
if(i & 1) {
int u = (i+1)/2;
queue<int> Q;
for(auto &v : adj[u]) Q.push(v);
for(int j = 0; j < 2 * n; ++j) {
if(j & 1) {
if(Q.empty()) {
ans[i][j] = u;
continue;
}
ans[i][j] = Q.front();
Q.pop();
} else {
ans[i][j] = u;
}
}
} else {
for(int j = 0; j < 2 * n; ++j) {
ans[i][j] = 1;
}
}
}
return ans;
}
