#include "worldmap.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <iostream>
#define pb push_back
using namespace std;
const int MX = 1005;
vector <int> v[MX], be[MX], de[MX];
vector <int> ord;
void dfs(int a, int p, vector<int> &fix) {
fix[a] = 1;
ord.pb(a);
for (int to : v[a]) {
if (to == p) continue;
if (fix[to]) {
be[a].pb(to);
} else {
de[a].pb(to);
dfs(to, a, fix);
ord.pb(a);
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
int n = N;
ord.clear();
vector <int> fix(n + 1, 0);
for (int i = 0; i <= N; i++) {
fix[i] = 0;
v[i].clear();
be[i].clear();
de[i].clear();
}
for (int i = 0; i < M; i++) {
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
dfs(1, 0, fix);
vector <vector<int>> ans;
ans.clear();
for (int i = 0; i < ord.size(); i++) {
vector <int> vec;
for (int j = 0; j < ord.size(); j++) {
vec.pb(ord[i]);
}
ans.pb(vec);
}
vector <vector <int>> res;
for (int i = 0; i < ord.size(); i++) {
res.pb(ans[i]);
int vert = ord[i];
if (be[vert].size()) {
vector <int> vec;
for (int j = 0; j < be[vert].size(); j++) {
vec.pb(be[vert][j]);
vec.pb(vert);
}
res.pb(vec);
vec.clear();
for(int i = 0; i < ord.size(); i++) {
vec.pb(vert);
}
res.pb(vec);
}
}
int sz = res.size();
for (int i = 0; i < sz; i++) {
while (res[i].size() < sz) {
res[i].pb(res[i].back());
}
}
return res;
}
