#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], kloc[N];
bool vis[N];
int wys[N];
vector<pair<int, int>> ed[N];
vector<int> red[N];
int wch[N];
vector<int> pth, cur, bd = {-1};
int gdz[N];
void DoDel(int n)
{
int v;
queue<int> q;
for(int i = 0; i < n; ++i)
{
wch[i] = ed[i].size();
if(wch[i] == 0) q.push(i);
}
while((int)q.size() > 0)
{
v = q.front(); q.pop();
del[v] = true;
for(int i = 0; i < (int)red[v].size(); ++i)
{
--wch[red[v][i]];
if(wch[red[v][i]] == 0) q.push(red[v][i]);
}
}
}
void MakeG(int n, int m)
{
for(int i = 0; i < n; ++i)
{ed[i].clear(); red[i].clear();}
for(int i = 0; i < m; ++i)
{
int a = U[i], b = V[i];
if(del[a] || del[b]) continue;
//if(rev[i]) swap(a, b);
ed[a].pb(make_pair(b, i));
red[b].pb(a);
}
}
bool DFS(int v, int av)
{
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(ed[v][i].nd == av || vis[ed[v][i].nd]) continue;
if(wys[ed[v][i].st] != 0)
{
cur.pb(ed[v][i].nd);
return true;
}
wys[ed[v][i].st] = wys[v] + 1;
if(DFS(ed[v][i].st, av))
{
cur.pb(ed[v][i].nd);
return true;
}
}
return false;
}
pair<vector<int>, vector<int>> Find(int v, int n, int av)
{
//cerr << "xd\n";
vector<int> ans, a1, a2;
bool abc;
for(int i = 0; i < n; ++i) wys[i] = 0;
wys[v] = 1;
abc = DFS(v, av);
if(!abc)
return make_pair(bd, bd);
reverse(cur.begin(), cur.end());
int x = min(wys[U[cur.back()]], wys[V[cur.back()]]);
ans = cur;
//cerr << "find: " << v << " " << x << " " << av << "\n";
//for(int i = 0; i < (int)cur.size(); ++i)
//cout << cur[i] << " ";
//cout << "\n";
cur.clear();
for(int i = 0; i <= x - 2; ++i)
a1.pb(ans[i]);
for(int i = x - 1; i < (int)ans.size(); ++i)
a2.pb(ans[i]);
//cerr << "xd\n";
return make_pair(a1, a2);
}
vector<int> Mrg1(vector<int> p1, vector<int> c1, vector<int> p2, vector<int> c2)
{
//cerr << "Mrg1\n";
vector<int> ans;
for(int i = 0; i < (int)p1.size(); ++i)
ans.pb(p1[i]);
for(int i = 0; i < (int)c1.size(); ++i)
ans.pb(c1[i]);
for(int i = p1.size() - 1; i >= 0; --i)
ans.pb(p1[i]);
for(int i = 0; i < (int)p2.size(); ++i)
ans.pb(p2[i]);
for(int i = 0; i < (int)c2.size(); ++i)
ans.pb(c2[i]);
for(int i = p2.size() - 1; i >= 0; --i)
ans.pb(p2[i]);
for(int i = 0; i < (int)p1.size(); ++i)
ans.pb(p1[i]);
for(int i = c1.size() - 1; i >= 0; --i)
ans.pb(c1[i]);
for(int i = p1.size() - 1; i >= 0; --i)
ans.pb(p1[i]);
for(int i = 0; i < (int)p2.size(); ++i)
ans.pb(p2[i]);
for(int i = c2.size() - 1; i >= 0; --i)
ans.pb(c2[i]);
for(int i = p2.size() - 1; i >= 0; --i)
ans.pb(p2[i]);
return ans;
}
vector<int> Mrg3(vector<int> p1, vector<int> c1, vector<int> p2, vector<int> c2)
{
//cerr << "Mrg1\n";
vector<int> ans;
for(int i = 0; i < (int)p1.size(); ++i)
ans.pb(p1[i]);
for(int i = 0; i < (int)c1.size(); ++i)
ans.pb(c1[i]);
for(int i = p1.size() - 1; i >= 0; --i)
ans.pb(p1[i]);
for(int i = 0; i < (int)p2.size(); ++i)
ans.pb(p2[i]);
for(int i = c2.size() - 1; i >= 0; --i)
ans.pb(c2[i]);
for(int i = p2.size() - 1; i >= 0; --i)
ans.pb(p2[i]);
return ans;
}
bool Check(vector<int> a, vector<int> b)
{
if(a.size() != b.size()) return false;
pair<int, int> m1 = make_pair(N, N), m2 = make_pair(N, N);
int l, r;
for(int i = 0; i < (int)a.size(); ++i)
m1 = min(m1, make_pair(a[i], i));
for(int i = 0; i < (int)b.size(); ++i)
m2 = min(m2, make_pair(b[i], i));
l = m1.nd; r = m2.nd;
for(int i = 0; i < (int)a.size(); ++i)
{
if(a[l] != b[r]) return false;
++l; ++r;
l %= (int)a.size();
r %= (int)b.size();
}
return true;
}
vector<int> DoC(int v, int n, int k)
{
for(int i = 0; i < k + 10; ++i) gdz[i] = -1;
pair<vector<int>, vector<int>> xd;
vector<int> p1, p2, c1, c2;
vector<int> a1, a2, b1, b2, m;
vector<int> ans;
xd = Find(v, n, -1);
p1 = xd.st; c1 = xd.nd;
if((int)p1.size() > 0 && p1[0] == -1) return bd;
int av = -1;
if((int)p1.size() > 0) av = p1[0];
else av = c1[0];
xd = Find(v, n, av);
p2 = xd.st; c2 = xd.nd;
if((int)p2.size() > 0 && p2[0] == -1) return bd;
if(Check(c1, c2))
return Mrg3(p1, c1, p2, c2);
int l = -1, r = -1;
for(int i = 0; i < (int)c2.size(); ++i)
gdz[c2[i]] = i;
for(int i = 0; i < (int)c1.size(); ++i)
if(gdz[c1[i]] != -1)
{
l = i; r = gdz[c1[i]]; break;
}
//cout << "LR: " << l << " " << r << "\n";
if(l == -1)
return Mrg1(p1, c1, p2, c2);
for(int i = 0; i < l; ++i)
a1.pb(c1[i]);
for(int i = 0; i < r; ++i)
b1.pb(c2[i]);
while(c1[l] == c2[r] && l < (int)c1.size() && r < (int)c2.size())
{
m.pb(c1[l]);
++l; ++r;
}
for(int i = l; i < (int)c1.size(); ++i)
a2.pb(c1[i]);
for(int i = 0; i < (int)p1.size(); ++i)
ans.pb(p1[i]);
for(int i = 0; i < (int)c1.size(); ++i)
ans.pb(c1[i]);
for(int i = p1.size() - 1; i >= 0; --i)
ans.pb(p1[i]);
//cerr << "xd\n";
for(int i = 0; i < (int)p2.size(); ++i)
ans.pb(p2[i]);
for(int i = 0; i < (int)b1.size(); ++i)
ans.pb(b1[i]);
for(int i = a1.size() - 1; i >= 0; --i)
ans.pb(a1[i]);
for(int i = a2.size() - 1; i >= 0; --i)
ans.pb(a2[i]);
for(int i = m.size() - 1; i >= 0; --i)
ans.pb(m[i]);
for(int i = b1.size() - 1; i >= 0; --i)
ans.pb(b1[i]);
for(int i = p2.size() - 1; i >= 0; --i)
ans.pb(p2[i]);
return ans;
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> XU, vector<int> XV)
{
vector<int> ans;
U = XU; V = XV;
MakeG(n, m);
DoDel(n);
if(del[0]) return false;
MakeG(n, m);
int v = 0;
bool abc = true;
do
{
if(kloc[v]) return false;
kloc[v] = true;
int il = 0;
for(int i = 0; i < (int)ed[v].size(); ++i)
if(!kloc[ed[v][i].st])
++il;
if(il == 0) return false;
if(il > 1) break;
abc = true;
for(int i = 0; i < (int)ed[v].size(); ++i)
if(!kloc[ed[v][i].st])
{
vis[ed[v][i].nd] = true;
pth.pb(ed[v][i].nd);
v = ed[v][i].st;
break;
}
}while(abc);
vector<int> xd = DoC(v, n, m);
if(xd[0] == -1) return false;
for(int i = 0; i < (int)pth.size(); ++i)
ans.pb(pth[i]);
for(int i = 0; i < (int)xd.size(); ++i)
ans.pb(xd[i]);
for(int i = pth.size() - 1; i >= 0; --i)
ans.pb(pth[i]);
return ans;
}
