#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
v<int> euler;
v<bool> vis;
v<v<int>> adj;
void dfs(int n) {
//cout << "DFS: " << n << endl;
vis[n] = true;
euler.push_back(n); euler.push_back(n); euler.push_back(n);
for (auto x : adj[n]) {
if (!vis[x]) {
dfs(x);
euler.push_back(n); euler.push_back(n); euler.push_back(n);
}
}
}
v<v<int>> ans;
void full(int i, int n) {
rep(j, 0, (int)ans[i].size()) {
ans[i][j] = n;
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
//cout << euler.size() << endl; for (auto x : euler) cout << x << " "; cout << endl;
adj.resize(N);
vis.assign(N, false);
rep(i, 0, M) {
int a = A[i];
int b = B[i];
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0);
int n = euler.size();
ans.assign(n, v<int>(n, 0));
for (int i =0; i < n; i += 3) {
full(i, euler[i]+1);
full(i+1, euler[i]+1);
full(i+2, euler[i]+1);
int cnt = 0;
int a = euler[i];
for (int j = 0; j < n-1; j += 2) {
cnt %= adj[a].size();
ans[i+1][j] = adj[a][cnt]+1;
ans[i+1][j+1] = a+1;
cnt++;
}
}
vis.clear();
adj.clear();
euler.clear();
return ans;
}
