#include "worldmap.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int mxN = 42; vector<int> adj[mxN], waiting[mxN]; vector<pair<int, int>> ord; int parent[mxN]; int find(int u){ if(parent[u] == u) return u; return parent[u] = find(parent[u]); } bool unite(int u, int v){ u = find(u), v = find(v); if(u == v) return 0; parent[u] = v; return 1; } void dfs(int u = 1, int par = 0){ if(par) ord.push_back({u, par}); for(auto it : adj[u]){ if(it ^ par) dfs(it, u); } if(par) ord.push_back({par, u}); } void reset(int N){ ord.clear(); for(int i = 1; i <= N; ++i){ adj[i].clear(); waiting[i].clear(); parent[i] = i; } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { reset(N); if(N == 1){ return {{1}}; } for(int i = 0; i < M; ++i){ if(unite(A[i], B[i])){ adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); }else{ waiting[A[i]].push_back(B[i]); } } dfs(1, 0); vector<vector<int>> ans; for(int i = 0; i < ord.size(); ++i){ vector<int> top_layer = {ord[i].first, ord[i].second}; vector<int> mid_layer; for(auto it : waiting[ord[i].first]){ if(mid_layer.size() == 1) mid_layer.push_back(ord[i].first); mid_layer.push_back(it); } if(mid_layer.size() == 1) mid_layer.push_back(ord[i].first); ans.push_back(top_layer); if(mid_layer.size()) ans.push_back(mid_layer); ans.push_back(top_layer); } for(int i = 0; i < (int) ans.size(); ++i){ while((int) ans.size() > (int) ans[i].size()) ans[i].push_back(ans[i].back()); } return ans; }