#include <iostream> #include <vector> #include <bitset> #include <random> #include <chrono> using namespace std; const int N = 100005; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<pair<int, int>> nei[N]; long long num[N]; int seen[N], Par[N]; int root(int v){ return (Par[v] == 0 ? v : Par[v] = root(Par[v])); } void dfs(int u, int p){ seen[u] = 1; for (auto [i, id] : nei[u]){ if (i == p) continue; dfs(i, u); if (num[i] == 0) cout<<i<<" "<<u<<'\n'; num[u] ^= num[i]; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin>>n>>m; for (int i=1, a, b;i<=m;i++){ long long rnd = 1, mod = 1e9 + 7; for (int j=1;j<=10;j++) rnd = rnd % mod * rng(); cin>>a>>b; if (root(a) == root(b)){ num[a] ^= rnd; num[b] ^= rnd; } else{ Par[root(a)] = root(b); nei[a].push_back({b, i}); nei[b].push_back({a, i}); } } for (int i=1;i<=n;i++){ if (seen[i] == 0) dfs(i, 0); } }