#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> visited;
vector<int> ret;
vector<vector<int>> graf, extras;
bool dfs(int curr, int depth) {
if (visited[curr]) return false;
visited[curr] = depth;
ret.push_back(curr+1);
bool skip = false;
for (int i = 0; i < graf[curr].size(); ++i) {
if (visited[graf[curr][i]] > depth) {
extras[i].push_back(graf[curr][i]+1);
}
if (visited[graf[curr][i]]) continue;
skip = true;
dfs(graf[curr][i], depth + 1);
}
if (skip) ret.push_back(curr+1);
return true;
}
std::vector<std::vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
ret.clear();
visited.assign(N, 0);
graf.assign(N, vector<int>{});
extras.assign(N, vector<int>{});
for (int i = 0; i < M; ++i) {
graf[A[i]-1].push_back(B[i] - 1);
graf[B[i]-1].push_back(A[i] - 1);
}
// cout<<"E"<<endl;
dfs(0, 1);
// cout<<"S"<<ret.size()<<endl;
vector<vector<int>> ans(ret.size() * 3, vector<int>(ret.size() * 3, 1));
for (int i = 0; i < ret.size(); ++i) {
for (int j = 0; j <= 2; ++j) {
// cout<<(3 * i + j)<<endl;
ans[i * 3 + j].assign(ret.size() * 3, ret[i]);
if (j == 1) {
for (int k = 0; k < extras[ret[i]-1].size(); ++k) {
ans[i*3+j][2*k] = extras[ret[i]-1][k];
}
}
}
}
return ans;
}
