#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> p, c, t;
vector<vector<int>> g;
void dfs(int cur, int par){
if (!c.empty()) return;
if (p[cur] != -1) return;
p[cur] = par;
for (int next : g[cur]){
if (next == par) continue;
if (p[next] != -1){
while (cur != next && cur != 0){
c.push_back(cur);
cur = p[cur];
}
c.push_back(cur);
while (cur != 0){
t.push_back(cur);
cur = p[cur];
}
t.push_back(cur);
reverse(c.begin(), c.end());
reverse(t.begin(), t.end());
return;
}
dfs(next, cur);
if (!c.empty()) return;
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
g.resize(N);
vector<vector<int>> v(N, vector<int>(N));
for (int i=0; i<M; i+=2){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
v[U[i]][V[i]] = i;
v[V[i]][U[i]] = i+1;
}
p.resize(N, -1);
dfs(0, 0);
if (c.empty()) return false;
/*for (int x : t) cout << x << " ";
cout << endl;
for (int x : c) cout << x << " ";
cout << endl;*/
vector<int> res;
for (int i=0; i<t.size()-1; i++) res.push_back(v[t[i]][t[i+1]]);
for (int i=0; i<c.size(); i++) res.push_back(v[c[i]][c[(i+1)%c.size()]]);
for (int i=c.size(); i>=1; i--) res.push_back(v[c[i%c.size()]][c[i-1]]);
for (int i=c.size(); i>=1; i--) res.push_back(v[c[i-1]][c[i%c.size()]]);
for (int i=0; i<c.size(); i++) res.push_back(v[c[(i+1)%c.size()]][c[i]]);
for (int i=(int)t.size()-1; i>=1; i--) res.push_back(v[t[i-1]][t[i]]);
return res;
}
