#include "islands.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
namespace
{
int K;
vector<int> path, vis, use, edge;
vector<pii> E[100000], R[100000];
int dfs(int u)
{
vis[u] = 1;
path.emplace_back(u);
for (auto [v, i] : E[u])
if (vis[v] == 0 && !use[i])
{
edge.emplace_back(i);
int res = dfs(v);
if (res != -1)
return res;
edge.pop_back();
}
else if (vis[v] == 1 && !use[i])
{
edge.emplace_back(i);
path.emplace_back(v);
return v;
}
path.pop_back();
vis[u] = 2;
return -1;
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
for (int i = 0; i < M; i += 2)
E[U[i]].emplace_back(pii(V[i], i));
vis.resize(N, 0);
use.resize(M, 0);
int res = dfs(0);
if (res == -1)
return false;
vector<int> chain, cyc;
vector<int> chE, cycE;
{
int i = 0;
for (; i < path.size(); i++)
{
chain.emplace_back(i);
if (path[i] == res)
break;
chE.emplace_back(edge[i]);
}
for (; i + 1 < path.size(); i++)
cycE.emplace_back(edge[i]);
path.clear();
}
vector<int> sol;
sol.insert(sol.end(), chE.begin(), chE.end());
sol.insert(sol.end(), cycE.begin(), cycE.end());
reverse(chE.begin(), chE.end());
sol.insert(sol.end(), chE.begin(), chE.end());
reverse(chE.begin(), chE.end());
for (int &i : chE)
i ^= 1;
reverse(cycE.begin(), cycE.end());
sol.insert(sol.end(), chE.begin(), chE.end());
sol.insert(sol.end(), cycE.begin(), cycE.end());
reverse(chE.begin(), chE.end());
sol.insert(sol.end(), chE.begin(), chE.end());
reverse(chE.begin(), chE.end());
return sol;
}
