//#include "insects.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#include <variant>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
int dfs(int s, vec<int>&c, vec<int>&r, vec<vec<pii>>&g, vec<bool>&bol, set<int>&je) {
bol[s] = 1;
je.insert(s);
for (auto &i : g[s]) {
if (je.find(i.ff) != je.end()) {
c.push_back(i.ss);
je.erase(s);
return i.ff;
}
if (bol[i.ff]) continue;
int x = dfs(i.ff, c, r, g, bol, je);
if (x == -2) {
r.push_back(i.ss);
je.erase(s);
return -2;
}
if (x != -1) {
c.push_back(i.ss);
je.erase(s);
if (x == s) return -2;
else return x;
}
}
je.erase(s);
return -1;
}
pair<vec<int>, vec<int>> cyc(vec<vec<pii>>&g, int s) {
vec<int> c, r;
set<int> je;
vec<bool> bol(g.size(), 0);
dfs(s, c, r, g, bol, je);
return { c, r };
}
int opacna(int x) {
if ((x % 2) == 0) {
return x + 1;
}
return x - 1;
}
void otoc(vec<int>& x) {
vec<int> y = x;
x.clear();
For(i, y.size()) {
x.push_back(y[y.size() - 1 - i]);
}
return;
}
void dfs2(int x, vec<bool>& bol, vec<vec<pii>>& g) {
bol[x] = 1;
for (auto i : g[x]) {
if (bol[i.ff]) continue;
dfs2(i.ff, bol, g);
}
return;
}
variant<bool, vector<int>> find_journey(int n, int m, vec<int> u, vec<int> v) {
vec<vec<pii>> g(n);
vec<int> poc(n, 0);
for (int i = 0; i < m; i+=2) {
g[u[i]].push_back({ v[i], i });
}
vec<bool> bol(n);
dfs2(0, bol, g);
for (int i = 0; i < m; i+=2) {
if (bol[u[i]] && bol[v[i]]) poc[v[i]]++;
}
vec<int> sp;
For(i, n) {
if (poc[i] == 0 && bol[i]) {
sp.push_back(i);
}
}
while (!sp.empty()) {
int x = sp.back(); sp.pop_back();
bol[x] = 0;
for (auto i : g[x]) {
poc[i.ff]--;
if (poc[i.ff] == 0) {
sp.push_back(i.ff);
}
}
}
bool ok = 0;
For(i, n) {
if (bol[i] == 1) {
ok = 1;
}
}
if (ok == 0) {
return false;
}
vec<int> odp;
pair<vec<int>, vec<int>> sracka = cyc(g, 0);
vec<int> c = sracka.ff;
vec<int> r = sracka.ss;
if (c.size() == 0) {
return false;
}
vec<int> c2;
otoc(r);
otoc(c);
For(i, c.size()) {
c2.push_back(opacna(c[c.size() - 1 - i]));
}
otoc(c2);
for (auto i : r) {
odp.push_back(i);
}
for (auto i : c) {
odp.push_back(i);
}
for (auto i : c2) {
odp.push_back(i);
}
otoc(c);
for (auto i : c) {
odp.push_back(i);
}
otoc(c2);
for (auto i : c2) {
odp.push_back(i);
}
otoc(r);
for (auto i : r) {
odp.push_back(i);
}
return odp;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
vec<int> u, v;
For(i, m) {
int a, b; cin >> a >> b;
u.push_back(a);
v.push_back(b);
}
variant<bool, vec<int>> odp = find_journey(n, m, u, v);
if (holds_alternative<bool>(odp)) {
cout << "odp is bool: " << get<bool>(odp) << endl;
}
else if (holds_alternative<vec<int>>(odp)) {
cout << "odp is vector: ";
for (int x : get<vec<int>>(odp)) {
cout << x << ' ';
}
cout << endl;
}
return 0;
}*/
