#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
constexpr int N = 1e5;
template <class T, size_t N>
class BufferedContainer {
T buf[N];
T *top = buf;
public:
void push_back(T value) { *top++ = value; }
void clear() { top = buf; }
T *begin() { return buf; }
T *end() { return top; }
};
int parent[N];
int sizeCC[N];
int parentCC[N];
int parent2CC[N];
// set<pair<int, int>> bridges;
int visted_token;
int visited[N];
BufferedContainer<int, N> pathA, pathB;
pair<int, int> bridge[N];
int find2CC(int v) {
if (v == -1)
return -1;
return parent2CC[v] == v ? v : parent2CC[v] = find2CC(parent2CC[v]);
}
int findCC(int v) {
v = find2CC(v);
return parentCC[v] == v ? v : parentCC[v] = findCC(parentCC[v]);
}
void make_root(int v) {
v = find2CC(v);
int root = v;
int child = -1;
pair<int, int> current = {-1, -1};
while (v != -1) {
int p = find2CC(parent[v]);
swap(current, bridge[v]);
parent[v] = child;
parentCC[v] = root;
child = v;
v = p;
}
sizeCC[root] = sizeCC[child];
}
void merge_path(int a, int b) {
pathA.clear();
pathB.clear();
int lca = -1;
visted_token++;
while (lca == -1) {
if (a != -1) {
a = find2CC(a);
pathA.push_back(a);
if (visited[a] == visted_token) {
lca = a;
break;
}
visited[a] = visted_token;
a = parent[a];
}
if (b != -1) {
b = find2CC(b);
pathB.push_back(b);
if (visited[b] == visted_token) {
lca = b;
break;
}
visited[b] = visted_token;
b = parent[b];
}
}
for (int v : pathA) {
parent2CC[v] = lca;
if (v == lca) break;
// cout << "bridge -= " << bridge[v].first << ' ' << bridge[v].second << " at " << v << endl;
bridge[v].first = -1;
// bridges.erase(minmax(v, parent[v]));
}
for (int v : pathB) {
parent2CC[v] = lca;
if (v == lca) break;
// cout << "bridge -= " << bridge[v].first << ' ' << bridge[v].second << " at " << v << endl;
bridge[v].first = -1;
// bridges.erase(minmax(v, parent[v]));
}
}
void add_edge(int u, int v) {
int a = find2CC(u);
int b = find2CC(v);
if (a == b) return;
int ca = findCC(a);
int cb = findCC(b);
if (ca == cb) {
merge_path(a, b);
return;
}
// bridges.insert(minmax(u, v));
if (sizeCC[ca] > sizeCC[cb]) {
swap(a, b);
swap(ca, cb);
}
make_root(a);
bridge[a] = {u, v};
parent[a] = parentCC[a] = b;
sizeCC[cb] += sizeCC[a];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
fill(parent, parent + n, -1);
iota(parent2CC, parent2CC + n, 0);
iota(parentCC, parentCC + n, 0);
fill(sizeCC, sizeCC + n, 1);
fill(bridge, bridge + n, pair<int, int>{-1, -1});
while (m--) {
int u, v;
cin >> u >> v;
add_edge(u - 1, v - 1);
}
// for (auto [u, v] : bridges) {
// cout << u + 1 << ' ' << v + 1 << '\n';
// }
for (int u = 0; u < n; u++) {
if (bridge[u].first == -1) continue;
cout << bridge[u].first + 1 << ' ' << bridge[u].second + 1 << '\n';
}
return 0;
}
