#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200100];
int ind[1000][1000];
bool vis[1000];
vector<int> ans;
bool dfs(int n, int p) {
if(vis[n]) return 0;
vis[n] = 1;
if(adj[n].size()>2-!(p+1)) {
int a=-1, b, c=-1, d;
for(auto i: adj[n])
if(i!=p) {
if(a<0)
a = ind[n][i], b = ind[i][n];
else if(c<0)
c = ind[n][i], d = ind[i][n];
}
ans.push_back(a);
ans.push_back(b);
ans.push_back(c);
ans.push_back(d);
ans.push_back(b);
ans.push_back(a);
ans.push_back(d);
ans.push_back(c);
return 1;
}
for(auto i: adj[n]) {
ans.push_back(ind[i][n]);
if(dfs(i, n)) {
ans.push_back(ind[i][n]);
return 1;
}
ans.pop_back();
}
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
for(int i = 0; i < M; i++)
adj[U[i]].push_back(V[i]), ind[U[i]][V[i]] = i;
if(dfs(0,-1)) {
return ans;
} else {
return false;
}
}
