#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
int n, m, can = 0;
vector<int> u, v, vis, adjj[1001];
vector<pair<int, int>> adj[1001];
void dfs(int node, vector<int> &ans)
{
vis[node] = 1;
if (node == 0)
{
if (adj[node].size() >= 2)
{
can = 1;
vector<int> cur(4);
for (int i = 0; i < 2; i++)
{
int bNum = adj[node][i].second;
cur[2 * i] = bNum;
cur[2 * i + 1] = (bNum % 2 == 1 ? bNum - 1 : bNum + 1);
ans.push_back(cur[2 * i]);
ans.push_back(cur[2 * i + 1]);
}
ans.push_back(cur[1]);
ans.push_back(cur[0]);
ans.push_back(cur[3]);
ans.push_back(cur[2]);
return;
}
}
else
{
if (adj[node].size() >= 3)
{
can = 1;
int i = 0, lboat1 = ans.back(), lboat2 = (lboat1 % 2 == 1 ? lboat1 - 1 : lboat1 + 1), sz = ans.size();
;
vector<int> cur(4);
for (auto k : adj[node])
{
if (i == 2)
break;
if (k.second == lboat2)
continue;
int bNum = k.second;
cur[2 * i] = bNum;
cur[2 * i + 1] = (bNum % 2 == 1 ? bNum - 1 : bNum + 1);
ans.push_back(cur[2 * i]);
ans.push_back(cur[2 * i + 1]);
i++;
}
ans.push_back(cur[1]);
ans.push_back(cur[0]);
ans.push_back(cur[3]);
ans.push_back(cur[2]);
for (int i = sz - 1; i >= 0; i--)
ans.push_back(ans[i]);
return;
}
}
for (auto a : adj[node])
{
if (vis[a.first])
continue;
ans.push_back(a.second);
dfs(a.first, ans);
if (can == 1)
return;
ans.pop_back();
}
}
vector<int> col, par, cycc, sts;
int cs, ce;
int cycle(int node)
{
col[node] = 1;
for (auto k : adjj[node])
{
if (col[k] == 0)
{
par[k] = node;
if (cycle(k))
return 1;
}
else if (col[k] == 1)
{
ce = node;
cs = k;
return 1;
}
}
col[node] = 2;
return 0;
}
variant<bool, std::vector<int>> sb4()
{
col.resize(n, 0);
par.resize(n, -1);
for (int i = 0; i < m; i += 2)
adjj[u[i]].push_back(v[i]);
int cyc = cycle(0);
if (cyc == 0)
return false;
cycc.push_back(cs);
int nod2 = ce;
while (nod2 != cs)
{
cycc.push_back(nod2);
nod2 = par[nod2];
}
cycc.push_back(cs);
sts.push_back(cs);
while (nod2 != -1)
{
sts.push_back(nod2);
nod2 = par[nod2];
}
reverse(cycc.begin(), cycc.end());
reverse(sts.begin(), sts.end());
if (cycc[0] == 0)
{
vector<int> mid;
int extra;
for (int i = 0; i < cycc.size() - 1; i++)
{
for (int j = 0; j < m; j += 2)
{
if (u[j] == cycc[i] && v[j] == cycc[i + 1])
{
mid.push_back(j);
if(i == 0)
extra = j + 1;
break;
}
}
}
vector<int> ans;
ans.insert(ans.end(), mid.begin(), mid.end());
reverse(mid.begin(), mid.end());
ans.push_back(extra);
ans.insert(ans.end(), mid.begin(), mid.end());
ans.push_back(extra);
return ans;
}
vector<int> fst, lst, mid;
for (int i = 0; i < sts.size() - 1; i++)
{
for (int j = 0; j < m; j += 2)
{
if (u[j] == sts[i] && v[j] == sts[i + 1])
{
fst.push_back(j);
lst.push_back(j + 1);
break;
}
}
}
for (int i = 0; i < cycc.size() - 1; i++)
{
for (int j = 0; j < m; j += 2)
{
if (u[j] == cycc[i] && v[j] == cycc[i + 1])
{
mid.push_back(j);
break;
}
}
}
vector<int> ans;
// fst half
ans.insert(ans.end(), fst.begin(), fst.end());
ans.insert(ans.end(), mid.begin(), mid.end());
reverse(fst.begin(), fst.end());
reverse(mid.begin(), mid.end());
ans.insert(ans.end(), fst.begin(), fst.end());
// sec half
ans.insert(ans.end(), lst.begin(), lst.end());
ans.insert(ans.end(), mid.begin(), mid.end());
reverse(lst.begin(), lst.end());
ans.insert(ans.end(), lst.begin(), lst.end());
return ans;
}
variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V)
{
n = N, m = M;
u = U, v = V;
vector<int> ans;
if (n <= 2)
{
if (m <= 2)
return false;
int z = 0;
vector<int> cur(3);
for (int i = 0; i < m; i++)
{
if (u[i] == 0)
{
if (z < 2)
cur[z] = i;
z++;
}
else
cur[2] = i;
}
if (z < 2 || z == m)
return false;
ans.resize(3);
ans[0] = cur[0];
ans[1] = cur[2];
ans[2] = cur[1];
for (int i = 0; i < 3; i++)
ans.push_back(ans[i]);
return ans;
}
return sb4();
// vis.resize(n, 0);
// for(int i=0;i<m;i+=2)
// {
// adj[u[i]].push_back({v[i], i});
// adj[v[i]].push_back({u[i], i + 1});
// }
// dfs(0, ans);
// if(can)
// return ans;
// return false;
}
