#include <algorithm>
#include <vector>
#include <cassert>
#include <vector>
struct Edge {
int from, to;
Edge(int const _from, int const _to) : from(_from), to(_to) {}
Edge reverse() const {
return Edge(to, from);
}
};
struct IndexedEdge {
int id;
Edge edge;
IndexedEdge(int const _id, Edge const &_edge): id(_id), edge(_edge) {}
IndexedEdge reverse() const {
return IndexedEdge(id, edge.reverse());
}
};
template<typename Ep, typename Wp>
struct WeightedEdge {
Ep edge;
Wp weight;
WeightedEdge(Ep const &_edge, Wp const &_weight): edge(_edge), weight(_weight) {}
};
template<typename EdgeType, bool directed = false>
struct Graph {
static constexpr bool is_directed = directed;
int n, m;
std::vector<EdgeType> edges;
explicit Graph(int const _n): n(_n), m(0){}
void addEdge(EdgeType const &edge) {
edges.push_back(edge), ++m;
}
};
template<typename Tp>
struct GridGraph {
std::vector<std::vector<Tp>>& grid;
int n, m;
std::vector<std::pair<int, int>> const dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
// const vector<pair<int, int>> dirs = {
// {-1, -1}, {-1, 0}, {-1, 1}, {1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}
// };
GridGraph(int _n = 0, int _m = 0) : n(_n), m(_m) {}
GridGraph(std::vector<std::vector<Tp>> const& _grid) : grid(_grid) {}
bool inBounds(int r, int c) const {
return 0 <= r && r < n && 0 <= c && c < m;
}
};
#include <random>
std::mt19937& rng() {
static std::random_device rd;
static std::mt19937 gen(rd());
return gen;
}
template<typename Tp>
Tp randInt(Tp a, Tp b) {
std::uniform_int_distribution<Tp> dist(a, b);
return dist(rng());
}
template<typename Tp>
Tp getRandomElement(std::vector<Tp> const& v) {
return v[randInt(0, static_cast<int>(v.size()) - 1)];
}
#include <vector>
template<typename Tp>
bool checkAnElementIsIn(std::vector<Tp> const& v, Tp const& e) {
for (Tp const& i: v) {
if (i == e) return true;
}
return false;
}
struct EulerianInfo {
bool has_eulerian_path;
std::vector<int> vertex_path; // vertexes in eulerian walk
std::vector<int> edge_path; // index edges in eulerian walk
};
template<bool directed>
EulerianInfo hasEulerianPath(Graph<IndexedEdge, directed> const& graph, int source = -1) {
int n = graph.n, m = graph.m;
assert(-1 <= source && source < n);
if (m == 0) {
return {true, {source == -1 ? randInt(0, n - 1) : source}, {}};
}
std::vector<int> vertex_path, edge_path;
std::vector<int> deg(n);
if constexpr (directed) {
for (IndexedEdge const &e : graph.edges) {
++deg[e.edge.from], --deg[e.edge.to];
}
int start = -1, end = -1;
for (int v = 0; v < n; v++) {
if (deg[v] == 1) {
if (start != -1)
return {false, {}, {}};
start = v;
} else if (deg[v] == -1) {
if (end != -1)
return {false, {}, {}};
end = v;
} else if (deg[v] != 0) {
return {false, {}, {}};
}
}
if (source != -1 && start != source) {
return {false, {}, {}};
}
if (source == -1) {
if (start == -1) source = graph.edges.front().edge.from;
else source = start;
}
} else {
for (IndexedEdge const &e : graph.edges) {
++deg[e.edge.from], ++deg[e.edge.to];
}
std::vector<int> starts;
for (int v = 0; v < n; v++) {
if (deg[v] & 1) starts.push_back(v);
}
if (starts.size() != 0 and starts.size() != 2) {
return {false, {}, {}};
}
if (source != -1 and starts.size() == 2 and !checkAnElementIsIn(starts, source)) {
return {false, {}, {}};
}
if (source == -1) {
if (starts.size() == 0) source = graph.edges.front().edge.from;
else source = getRandomElement(starts);
}
}
std::vector<std::vector<std::pair<int, int>>> adj(n);
std::vector<bool> used(m);
for (IndexedEdge const &e : graph.edges) {
int u = e.edge.from, v = e.edge.to, id = e.id;
adj[u].push_back({v, id});
if constexpr (!directed) adj[v].push_back({u, id});
}
std::vector<std::pair<int, int>> _stack = {{source, -1}};
while (!_stack.empty()) {
auto &[u, id_u] = _stack.back();
while (!adj[u].empty() && used[adj[u].back().second]) {
adj[u].pop_back();
}
if (adj[u].empty()) {
_stack.pop_back();
vertex_path.push_back(u);
if (id_u != -1) edge_path.push_back(id_u);
} else {
auto &[v, id_v] = adj[u].back();
adj[u].pop_back();
if (!used[id_v]) {
used[id_v] = true;
_stack.push_back({v, id_v});
}
}
}
if (edge_path.size() < m) {
return {false, {}, {}};
}
reverse(vertex_path.begin(), vertex_path.end());
reverse(edge_path.begin(), edge_path.end());
return {true, vertex_path, edge_path};
}
#include <iostream>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
Graph<IndexedEdge> graph(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph.addEdge({i, {--u, --v}});
}
const auto [flag, vs, es] = hasEulerianPath(graph);
vector<vector<int>> pos(n);
assert(vs.front() == vs.back());
for (int i = 0; i <= m; i++) {
pos[vs[i]].push_back(i);
}
vector<pair<int, int>> cycles = {{0, m}};
for (int i = 1; i < m; i++) {
const int v = vs[i];
int p = lower_bound(pos[v].begin(), pos[v].end(), cycles.back().second) - pos[v].begin() - 1;
if (0 <= p and i < pos[v][p]) {
cycles.push_back({i, pos[v][p]});
}
}
reverse(cycles.begin(), cycles.end());
for (int i = 0; i < cycles.size(); i++) {
if (i == 0) {
for (int j = cycles[i].first; j < cycles[i].second; j++) {
cout << vs[j] + 1 << ' ';
}
cout << '\n';
} else {
for (int j = cycles[i].first; j < cycles[i - 1].first; j++) {
cout << vs[j] + 1 << ' ';
}
for (int j = cycles[i - 1].second; j < cycles[i].second; j++) {
cout << vs[j] + 1 << ' ';
}
cout << '\n';
}
}
return 0;
}
