#include <bits/stdc++.h>
#include "islands.h"
#include <variant>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10 , M = 2e5 + 10;
int n , m , dis[N] , st_tim[N] , fn_tim[N] , tim;
vector <pair<int , int>> adj[N];
pair <int , int> par[N] , bh[N];
bool marked[N];
void Dfs(int v)
{
marked[v] = true;
st_tim[v] = tim;
tim++;
for(auto u : adj[v])
{
if(!marked[u.F])
{
par[u.F] = make_pair(v , u.S);
dis[u.F] = dis[v] + 1;
Dfs(u.F);
}
else if(fn_tim[u.F] == 0)
{
if(bh[v].F == -1 || dis[bh[v].F] < dis[u.F])
bh[v] = u;
}
}
fn_tim[v] = tim;
}
vector <int> Solve1(int v)
{
vector <int> p;
int now = v;
while(now != 0)
{
p.push_back(par[now].S);
now = par[now].F;
}
reverse(p.begin() , p.end());
vector <int> vec;
for(auto u : adj[v]) if(u.S != (par[v].S ^ 1))
vec.push_back(u.S);
vector <int> res;
for(auto u : p)
res.push_back(u);
reverse(p.begin() , p.end());
res.push_back(vec[0]);
res.push_back((vec[0] ^ 1));
res.push_back(vec[1]);
res.push_back((vec[1] ^ 1));
res.push_back((vec[0] ^ 1));
res.push_back(vec[0]);
res.push_back((vec[1] ^ 1));
res.push_back(vec[1]);
for(auto u : p)
res.push_back(u);
return res;
}
variant<bool , vector <int>> find_journey(int nn , int mm , vector <int> U , vector <int> V)
{
n = nn;
m = mm;
for(int i = 0 ; i < m ; i++) if(U[i] <= 2 && V[i] <= 2)
adj[U[i]].push_back({V[i] , i});
if(n <= 2)
return false;
vector <int> res;
for(int i = 0 ; i <= 2 ; i++)
sort(adj[i].begin() , adj[i].end());
res.push_back(adj[0][0].S);
res.push_back(adj[1][0].S);
res.push_back(adj[0][1].S);
res.push_back(adj[2][0].S);
res.push_back(adj[1][0].S);
res.push_back(adj[0][0].S);
res.push_back(adj[2][0].S);
res.push_back(adj[0][1].S);
return res;
}
