#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define ln '\n';
template <class F, class S>
bool chmin(F &u, const S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
int n = N, m = M;
// subtask #3
vector <vector<int>> adj(n);
map <pair<int,int>,vector<int>> id;
for ( int i = 0; i < m; i++ ){
adj[U[i]].pb(V[i]);
id[{U[i], V[i]}].pb(i);
}
vector <int> d(n, n + 1), fa(n, -1);
queue <int> q;
q.push(0); d[0] = 0;
ar <int,2> mt = {-1, -1};
while ( !q.empty() ){
int u = q.front();
q.pop();
for ( auto &v: adj[u] ){
if ( chmin(d[v], d[u] + 1) ){
q.push(v); fa[v] = u;
} else if ( d[v] == d[u] + 1 ){
mt = {u, v};
}
}
}
map <int,int> mp;
int cnt = 0;
for ( auto &x: d ){
if ( x != n + 1 ){
mp[x] += 1;
cnt += 1;
}
}
if ( (int)mp.size() == cnt && mt[0] == -1 ){
return false;
}
if ( (int)mp.size() == cnt ){ // multi_edge
vector <int> path;
int u = mt[1];
while ( u != -1 ){
path.pb(u);
u = fa[u];
}
reverse(all(path));
int s = path.size();
vector <int> ans;
for ( int i = 0; i + 1 < s; i++ ){
ans.pb(id[{path[i], path[i + 1]}][0]);
}
auto tmp = ans;
ans.pb(id[{mt[1], mt[0]}][0]);
ans.pb(id[{mt[0], mt[1]}][1]);
ans.pb(id[{mt[1], mt[0]}][1]);
ans.pb(id[{mt[1], mt[0]}][0]);
ans.pb(id[{mt[0], mt[1]}][1]);
ans.pb(id[{mt[1], mt[0]}][1]);
for ( int i = s - 2; i >= 0; i-- ){
ans.pb(tmp[i]);
}
return ans;
} else{
int u = -1, v = -1;
for ( int i = 0; i < n; i++ ){
for ( int j = i + 1; j < n; j++ ){
if ( fa[i] == -1 ) continue;
if ( fa[i] == fa[j] ){
u = i, v = j;
}
}
}
assert(u != -1 && v != -1);
//~ cout << "Debug : " << u << " " << v << ln;
vector <int> path;
int x = fa[u];
while ( x != -1 ){
path.pb(x);
x = fa[x];
}
reverse(all(path));
int s = path.size();
vector <int> ans;
for ( int i = 0; i + 1 < s; i++ ){
ans.pb(id[{path[i], path[i + 1]}][0]);
}
auto tmp = ans;
x = fa[u];
ans.pb(id[{x, v}][0]);
ans.pb(id[{v, x}][0]);
ans.pb(id[{x, u}][0]);
ans.pb(id[{u, x}][0]);
ans.pb(id[{x, v}][0]);
ans.pb(id[{v, x}][0]);
ans.pb(id[{x, u}][0]);
ans.pb(id[{u, x}][0]);
for ( int i = s - 2; i >= 0; i-- ){
ans.pb(tmp[i]);
}
return ans;
}
return {};
}
