#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
vector<int> U, V;
bool del[N];
bool vis[N], stay[N];
set<pair<int, int>> ed[N];
set<int> red[N];
vector<int> cur, pth, zb1, zb2;
int wch[N];
bool DFS(int v)
{
vis[v] = true;
//cerr << v << "\n";
for(set<pair<int, int>>::iterator it = ed[v].begin(); it != ed[v].end(); ++it)
{
if(vis[(*it).st])
{
cur.pb((*it).nd);
return true;
}
if(DFS((*it).st))
{
cur.pb((*it).nd);
return true;
}
}
return false;
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> XU, vector<int> XV)
{
vector<int> ans;
queue<int> q;
U = XU; V = XV;
int v = 0;
for(int i = 0; i < m; ++i)
{
ed[U[i]].insert(make_pair(V[i], i));
red[V[i]].insert(U[i]);
++wch[U[i]];
}
for(int i = 0; i < n; ++i)
if(wch[i] == 0) q.push(i);
while(wch[v] == 1)
{
pth.pb((*ed[v].begin()).nd);
v = (*ed[v].begin()).st;
}
while(q.size() > 0)
{
if(wch[v] == 0) return false;
int u = q.front(); q.pop();
del[u] = true;
for(set<int>::iterator it = red[u].begin(); it != red[u].end(); ++it)
{
--wch[*it];
ed[*it].erase(ed[*it].lower_bound(make_pair(u, 0)));
if(wch[*it] == 0)
q.push(*it);
}
while(wch[v] == 1)
{
for(set<int>::iterator it = red[v].begin(); it != red[v].end(); ++it)
{
--wch[*it];
ed[*it].erase(ed[*it].lower_bound(make_pair(v, 0)));
if(wch[*it] == 0)
q.push(*it);
}
pth.pb((*ed[v].begin()).nd);
v = (*ed[v].begin()).st;
}
}
if(del[v] || wch[v] <= 1) return false;
for(int i = 0; i < n; ++i) ed[i].clear();
for(int i = 0; i < m; ++i)
if(!del[V[i]] && !del[U[i]])
ed[U[i]].insert(make_pair(V[i], i));
DFS(v);
reverse(cur.begin(), cur.end());
//cout << "Cur1\n";
//for(int i = 0; i < (int)cur.size(); ++i)
//cout << cur[i] << " ";
//cout << "\n";
zb1 = cur;
ed[U[zb1[0]]].erase(make_pair(V[zb1[0]], zb1[0]));
cur.clear();
DFS(v);
reverse(cur.begin(), cur.end());
//cout << "Cur2\n";
//for(int i = 0; i < (int)cur.size(); ++i)
//cout << cur[i] << " ";
//cout << "\n";
for(int i = 0; i < n; ++i) ed[i].clear();
zb2 = cur;
cur.clear();
for(int i = 0; i < (int)zb1.size(); ++i)
{
int j = zb1[i];
stay[j] = true;
//ed[U[j]].insert(make_pair(V[j], j));
}
for(int i = 0; i < (int)zb2.size(); ++i)
stay[zb2[i]] = true;
for(int i = 0; i < m; ++i)
if(!del[V[i]] && !del[U[i]] && stay[i])
ed[U[i]].insert(make_pair(V[i], i));
int lst = -1, cnt = 0, beg = v;
cur = pth;
while(true)
{
//cerr << "xd " << v << " " << beg << "\n";
if(v == beg) ++cnt;
if(cnt == 13) break;
for(set<pair<int, int>>::iterator it = ed[v].begin(); it != ed[v].end(); ++it)
if((*it).nd != lst)
{
int ne = (*it).st, num = (*it).nd;
ed[v].erase(it);
ed[ne].insert(make_pair(v, num));
lst = num;
cur.pb(num);
v = ne;
break;
}
}
for(int i = pth.size() - 1; i >= 0; --i)
cur.pb(pth[i]);
return cur;
}
