#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int dept[MAXN];
bool vis[MAXN];
vector<pii> a[MAXN];
vector<int> p, q, ans;
void dfs(int v, int i){
vis[v] = 1;
dept[v] = q.size();
if(a[v].size() > 2 && ans.empty()){
for(auto & j : q) ans.append(j);
for(auto & [u, j] : a[v]){
if((i ^ j) < 2) continue;
p.append(j);
}
for(auto & j : p){
ans.append(j);
ans.append(j ^ 1);
}
for(auto & j : p){
ans.append(j ^ 1);
ans.append(j);
}
for(int j = q.size(); j > 0; j--)
ans.append(q[j - 1]);
}
for(auto & [u, j] : a[v]){
if((i ^ j) < 2) continue;
if(!vis[u]){
q.append(j);
dfs(u, j);
q.pop_back();
}
else if(ans.empty()){
q.append(j);
for(int k = dept[u]; k < q.size(); k++)
p.append(q[k]);
for(auto & k : q)
ans.append(k);
reverse(all(p));
for(auto & k : p)
ans.append(k ^ 1);
for(auto & k : p)
ans.append(k);
reverse(all(p));
for(auto & k : p)
ans.append(k ^ 1);
for(int k = dept[u]; k > 0; k--)
ans.append(q[k - 1]);
}
}
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v){
for(int i = 0; i < m; i++)
a[u[i]].append({v[i], i});
dfs(0, m);
if(a[0].size() > 1 && ans.empty()){
for(auto & [u, j] : a[0])
p.append(j);
for(auto & j : p){
ans.append(j);
ans.append(j ^ 1);
}
for(auto & j : p){
ans.append(j ^ 1);
ans.append(j);
}
}
if(ans.empty()) return false;
return ans;
}
