#include "worldmap.h"
#include <functional>
using namespace std;
// Helper function to find a sequence of integers satisfying the conditions
std::vector<int> find_sequence(int N, const std::vector<std::vector<int>>& adjacency_list) {
std::vector<int> sequence;
std::vector<bool> visited(N, false);
std::function<void(int)> dfs = [&](int node) {
visited[node] = true;
sequence.push_back(node);
for (int neighbor : adjacency_list[node]) {
if (visited[neighbor]) continue;
dfs(neighbor);
sequence.push_back(node);
}
};
dfs(0);
return sequence;
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
if (N == 1) {
return {{1}};
}
std::vector<std::vector<int>> adjacency_list(N);
for (int i = 0; i < M; ++i) {
adjacency_list[A[i] - 1].push_back(B[i] - 1);
adjacency_list[B[i] - 1].push_back(A[i] - 1);
}
std::vector<int> sequence = find_sequence(N, adjacency_list);
std::vector<int> first_occurrence(sequence.size(), 0);
std::vector<bool> seen(N, false);
for (size_t i = 0; i < sequence.size(); ++i) {
if (!seen[sequence[i]]) {
first_occurrence[i] = 1;
seen[sequence[i]] = true;
}
}
for (int i = first_occurrence.size() - 1; i >= 0; --i) {
if (first_occurrence[i]) {
sequence.resize(i + 1);
first_occurrence.resize(i + 1);
break;
}
}
std::vector<std::vector<int>> ans;
for (int i = 0; i < sequence.size(); ++i) {
int node = sequence[i];
if (first_occurrence[i]) {
std::vector<int> neighbors;
for (int neighbor : adjacency_list[node]) {
if (neighbor > node) {
neighbors.push_back(neighbor + 1);
neighbors.push_back(node + 1);
}
}
if (!neighbors.empty()) {
neighbors.pop_back();
}
ans.push_back({node + 1});
if (!neighbors.empty()) {
ans.push_back(neighbors);
ans.push_back({node + 1});
}
} else {
ans.push_back({node + 1});
}
}
ans.pop_back();
int mx_len = ans.size();
for (int i = 0; i < ans.size(); ++i) {
if (ans[i].size() > mx_len) {
mx_len = ans[i].size();
}
}
for (int i = 0; i < ans.size(); ++i) {
int last = ans[i].back();
while (ans[i].size() < mx_len) {
ans[i].push_back(last);
}
}
while (ans.size() < mx_len) {
ans.push_back(ans.back());
}
return ans;
}
