/*
File created on 05/27/2021 at 15:50:04.
Link to problem: https://oj.uz/problem/view/BOI14_postmen
Description: Hierholzer's algorithm for eulerian cycle + separation in "mini" cycles
Time complexity: O(N+M)
Space complexity: O(N+M)
Status: TLE
Copyright: Ⓒ 2021 Francois Vogel
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
#define pib pair<int, *obj>
#define f first
#define s second
#define pb push_back
#define ins insert
#define int ll
#define ll long long
int encode(int a, int b) { return (min(a, b)*1000000+max(a, b)); }
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, nbEdges;
cin >> n >> nbEdges;
vector<int> graph [n];
for (int i = 0; i < nbEdges; i++) {
int nodeA, nodeB;
cin >> nodeA >> nodeB;
nodeA--;
nodeB--;
graph[nodeA].pb(nodeB);
graph[nodeB].pb(nodeA);
}
unordered_set<int> usedEdges;
vector<int> circuit, path, st;
bool as [n];
memset(as, false, n);
path.pb(0);
while (!path.empty()) {
while (!graph[path.back()].empty() and usedEdges.find(encode(path.back(), graph[path.back()].back())) != usedEdges.end()) graph[path.back()].pop_back();
if (graph[path.back()].empty()) {
circuit.pb(path.back());
path.pop_back();
int i = circuit.back();
if (as[i]) {
while (st.back() != i) {
as[st.back()] = false;
cout << st.back()+1 << " ";
st.pop_back();
}
st.pop_back();
cout << i+1 << " " << endl;
}
as[i] = true;
st.pb(i);
}
else {
int nn = graph[path.back()].back();
graph[path.back()].pop_back();
usedEdges.insert(encode(path.back(), nn));
path.pb(nn);
}
}
// bool as [n];
// memset(as, false, n);
// vector<int> st;
// for (int i : circuit) {
// if (as[i]) {
// while (st.back() != i) {
// as[st.back()] = false;
// cout << st.back()+1 << " ";
// st.pop_back();
// }
// st.pop_back();
// cout << i+1 << " " << endl;
// }
// as[i] = true;
// st.pb(i);
// }
int d = 0;
d++;
}
