Problem: Find bridges of an undirected graph G(V, E).

A bridge (also known as a cut-edge) is an edge whose deletion increase the number of connected components.

Constraints

* 1 ≤ |V| ≤ 100,000
* 0 ≤ |E| ≤ 100,000
* The graph is connected
* There are no parallel edges
* There are no self-loops

Input


|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1


, where |V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (undirected).

Output

A list of bridges of the graph ordered by name. For each bridge, names of its end-ponints, source and target (source < target), should be printed separated by a space. The sources should be printed ascending order, then the target should also be printed ascending order for the same source.

Examples

Input

4 4
0 1
0 2
1 2
2 3


Output

2 3


Input

5 4
0 1
1 2
2 3
3 4


Output

0 1
1 2
2 3
3 4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define mp(a,b) make_pair((a),(b))
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int INF=1<<30;
const long long int INFLL=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

const int max_v=100000;
vector<int> graph[max_v];
bool used_v[max_v];
map<int,bool> used_e[max_v];
int ord[max_v],lowlink[max_v];
vector<pii> bridges;

void dfs(int v,int &k){
    used_v[v]=true;
    ord[v]=lowlink[v]=k++;
    for(int u:graph[v]){
        if(!used_v[u]){
            used_e[v][u]=true;
            dfs(u,k);
            lowlink[v]=min(lowlink[v],lowlink[u]);
            if(ord[v]<lowlink[u]) bridges.push_back(make_pair(min(v,u),max(v,u)));
        }else if(!used_e[u][v]) lowlink[v]=min(lowlink[v],ord[u]);
    }
}

void solve(){
    int v,e;
    cin >> v >> e;
    
    vector<pii> edges(e);
    rep(i,0,e){
        int s,t;
        cin >> s >> t;
        graph[s].push_back(t);
        graph[t].push_back(s);
        if(s>t) swap(s,t);
        edges[i]=make_pair(s,t);
    }
    
    int k=0;
    dfs(0,k);
    
    sort(bridges.begin(),bridges.end());
    
    for(auto &e:bridges) cout << e.first << " " << e.second << endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	solve();
	return 0;
}