#include "worldmap.h"
#include <iostream>
#include <set>
#define vec vector
#define For(i, n) for(int i = 0; i < (int)n; i++)
using namespace std;
vec<vec<int>> g;
vec<int> bol;
vec<int> o;
vec<vec<int>> boc;
vec<int> vrst;
void dfs(int x, vec<int>&p, int pr = -1){
bol[x] = 1;
p.push_back(x);
for(auto i : g[x]){
if(i == pr) continue;
if(bol[i]) {
if(vrst[i] < vrst[x]) boc[i].push_back(x);
continue;
}
vrst[i] = vrst[x] + 1;
o[i] = x;
dfs(i, p, x);
p.push_back(x);
}
return;
}
void vypis(vec<int>&p){
for(auto i : p){
cerr << i << ' ';
}
cerr << endl;
return;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vec<vec<int>> odp;
g.clear();
bol.clear();
o.clear();
boc.clear();
vrst.clear();
g.resize(N);
bol.resize(N, false);
vrst.resize(N, 0);
o.resize(N, -1);
boc.resize(N);
cerr << "cvok" << endl;
For(i, M){
int a, b; a = A[i], b = B[i]; a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
cerr << "cvok" << endl;
vec<int> p;
dfs(0, p);
vec<int> deti(N, 0);
cerr << "cvok" << endl;
For(i, N){
if(o[i] == -1) continue;
deti[o[i]]++;
}
vec<int> prec;
odp.push_back(p);
cerr << "cvok" << endl;
set<int> vym;
for(;;){
bool koniec = 0;
vypis(p);
For(i, p.size()){
if(deti[p[i]] == 0) {
cerr << "som tu: " << i << endl;
vym.insert(p[i]);
cerr << "ok" << endl;
if(p[i] == 0){
koniec = 1;
break;
}
p[i] = o[p[i]];
}
}
if(koniec) {cerr << "tu " << endl; break;}
vec<int> vp = p;
//tu ries tie spatne dfs hrany
odp.push_back(p);
odp.push_back(vp);
odp.push_back(p);
for(auto i : vym){
deti[o[i]]--;
}
}
if(odp.size() > p.size()){
int os = odp.size();
For(i, odp.size()){
odp[i].resize(os, 0);
}
}
if(p.size() > odp.size()){
int ps = p.size(), os = odp.size();
For(i, ps - os){
odp.push_back(p);
}
}
cerr << "koncim" << endl;
For(i, odp.size()){
For(j, odp[i].size()){
odp[i][j]++;
}
}
return odp;
}
