#include "islands.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define iint signed
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define pii pair<int,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
template<typename S> void chmin(S &x,S y) { x=min(x,y); }
template<typename S> void chmax(S &x,S y) { x=max(x,y); }
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
std::variant<bool, std::vector<iint>> find_journey(
iint N, iint M, std::vector<iint> U, std::vector<iint> V) {
int n=N,m=M;
Graphw g(n);
REP(i,m) {
if(i%2==0)g[U[i]].pb({V[i],i});
}
Vi vis(n);
Vi cyc,pat;
Vi pre(n,-1),prei(n);
auto dfs=[&](auto dfs,int u) ->bool {
ope(u)
vis[u]=1;
for(auto [v,id]:g[u]){
op(v)ope(vis[v])
if(vis[v]) {
int now=u;
int __=0;
while(now!=v) {
// assert(__++<=n);
cyc.pb(prei[now]);
now=pre[now];
}
__=0;
reverse(ALL(cyc));
cyc.pb(id);
while(now!=0) {
// assert(__++<=n);
pat.pb(prei[now]);
now=pre[now];
}
reverse(ALL(pat));
return 1;
}
ope("ok")
prei[v]=id;
pre[v]=u;
if(dfs(dfs,v)) return 1;
}
return 0;
};
// dfs(dfs,0);
ope("ok")
if(!dfs(dfs,0)) return false;
oparr(pat)oparr(cyc)
vector<iint> _an;
int p=SZ(pat),c=SZ(cyc);
REP(i,p) _an.pb(pat[i]);
REP(i,c-1) _an.pb(cyc[i]);
_an.pb(cyc[c-1]);
REP(i,c-1) _an.pb(cyc[i]^1);
RREP(i,c-1) _an.pb(cyc[i]);
_an.pb(cyc[c-1]);
_an.pb(cyc[c-1]^1);
REP(i,c-1) _an.pb(cyc[i]);
RREP(i,c-1) _an.pb(cyc[i]^1);
_an.pb(cyc[c-1]^1);
RREP(i,c-1) _an.pb(cyc[i]);
RREP(i,p) _an.pb(pat[i]);
// REP(i,SZ(an0)) _an.pb(an0[i]);
// for(int x:an) _an.pb(x);
// for(int x:an) _an.pb(x^1);
// RREP(i,SZ(an0)) _an.pb(an0[i]);
// return _an;
return _an;
}
/*
4 8
0 1
1 0
1 2
2 1
1 3
3 1
2 3
3 2
4 12
0 1
1 0
0 2
2 0
0 3
3 0
1 2
2 1
1 3
3 1
2 3
3 2
4 8
0 1
0 1
1 2
1 2
2 3
2 3
3 1
3 1
*/
