#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= ll(l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
namespace s1 {
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
vector<int> v[2];
Loop (i,0,M)
v[U[i]].push_back(i);
if (v[0].size() < 2 || v[1].size() < 1)
return false;
vector<int> ans = {
v[0][0], v[1][0], v[0][1], v[0][0], v[1][0], v[0][1],
};
return ans;
}
}
namespace s2 {
const int N = 512;
int a[N][N];
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
if (N == 2)
return false;
Loop (i,0,M)
a[U[i]][V[i]] = i;
vector<int> ans = {
a[0][1], a[1][0], a[0][2], a[2][0], a[1][0], a[0][1], a[2][0], a[0][2],
};
return ans;
}
}
namespace s3 {
const int N = 100'010;
vector<pii> A[N];
bool vis[N];
bool anc[N];
vector<int> ans;
void answer(int v, int p)
{
vector<int> vec;
for (auto [u, e] : A[v]) {
if (u == p)
continue;
vec.push_back(e);
}
vector<int> tmp = ans;
ans.push_back(vec[0]^0);
ans.push_back(vec[0]^1);
ans.push_back(vec[1]^0);
ans.push_back(vec[1]^1);
ans.push_back(vec[0]^1);
ans.push_back(vec[0]^0);
ans.push_back(vec[1]^1);
ans.push_back(vec[1]^0);
reverse(tmp.begin(), tmp.end());
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
bool dfs(int v, int p)
{
if (A[v].size() - (p != -1) >= 2) {
answer(v, p);
return 1;
}
for (auto [u, e] : A[v]) {
if (u == p)
continue;
ans.push_back(e);
if (dfs(u, v))
return 1;
ans.pop_back();
}
return 0;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
Loop (i,0,M)
A[U[i]].push_back({V[i], i});
if (!dfs(0, -1))
return false;
return ans;
}
}
namespace s4 {
const int N = 100'010;
vector<pii> A[N];
bool vis[N];
bool anc[N];
int height[N];
vector<int> ans;
void answer(int v, int u, int e)
{
ans.push_back(e);
int cnt = height[u] - height[v] + 1;
int pre = ans.size() - cnt;
Loop (i,pre,pre+cnt)
ans.push_back(ans[i]^1);
LoopR (i,pre,pre+cnt)
ans.push_back(ans[i]^0);
LoopR (i,pre,pre+cnt)
ans.push_back(ans[i]^1);
LoopR (i,0,pre)
ans.push_back(ans[i]);
}
bool dfs(int v, int h)
{
height[v] = h;
vis[v] = 1;
anc[v] = 1;
for (auto [u, e] : A[v]) {
if (anc[u]) {
answer(u, v, e);
return 1;
}
if (vis[u])
continue;
ans.push_back(e);
if (dfs(u, h+1))
return 1;
ans.pop_back();
}
anc[v] = 0;
return 0;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
for (int i = 0; i < M; i += 2)
A[U[i]].push_back({V[i], i});
if (!dfs(0, 0))
return false;
return ans;
}
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
if (N == 2)
return s1::find_journey(N, M, U, V);
bool is3 = M%2 == 0;
for (int i = 0; i+2 <= M; i += 2)
is3 &= U[i] == V[i+1] && U[i+1] == V[i];
if (is3)
return s3::find_journey(N, M, U, V);
bool is4 = M%2 == 0;
for (int i = 0; i+2 <= M; i += 2)
is4 &= U[i] == U[i+1] && V[i+1] == V[i];
if (is4)
return s4::find_journey(N, M, U, V);
return s2::find_journey(N, M, U, V);
}
