Problem: Bertown has n junctions and m bidirectional roads. We know that one can get from any junction to any other one by the existing roads. 

As there were more and more cars in the city, traffic jams started to pose real problems. To deal with them the government decided to make the traffic one-directional on all the roads, thus easing down the traffic. Your task is to determine whether there is a way to make the traffic one-directional so that there still is the possibility to get from any junction to any other one. If the answer is positive, you should also find one of the possible ways to orient the roads.

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 3·105) which represent the number of junctions and the roads in the town correspondingly. Then follow m lines, each containing two numbers which describe the roads in the city. Each road is determined by two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the numbers of junctions it connects.

It is guaranteed that one can get from any junction to any other one along the existing bidirectional roads. Each road connects different junctions, there is no more than one road between each pair of junctions.

Output

If there's no solution, print the single number 0. Otherwise, print m lines each containing two integers pi and qi — each road's orientation. That is the traffic flow will move along a one-directional road from junction pi to junction qi. You can print the roads in any order. If there are several solutions to that problem, print any of them.

Examples

Input

6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5


Output

1 2
2 3
3 1
4 5
5 6
6 4
4 2
3 5


Input

6 7
1 2
2 3
1 3
4 5
4 6
5 6
2 4


Output

0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int N = 100010;
const int M = 300010;
const long long INF = 1ll << 60;
const int inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
std::vector<std::pair<int, int> > ans;
class Graph {
 public:
  void Init(int n) {
    e_.clear();
    e_.push_back(Edge(0, 0, 1, 0));
    m_ = 0;
    n_ = n;
    hd_.assign(n + 1, 0);
    vis_.assign(n + 1, false);
    connected_num_ = 0;
    for (int i = 1; i <= n; ++i) {
      deg_in_[i] = 0;
    }
  }
  void Init(int n, long long w[]) {
    e_.clear();
    e_.push_back(Edge(0, 0, 1, 0));
    m_ = 0;
    n_ = n;
    hd_.assign(n + 1, 0);
    vis_.assign(n + 1, false);
    connected_num_ = 0;
    for (int i = 1; i <= n; ++i) {
      deg_in_[i] = 0;
      weight[i] = w[i];
    }
  }
  void Add(int u, int v, long long w = 1ll, int type = 0) {
    Edge edge(v, hd_[u], w, type);
    e_.push_back(edge);
    hd_[u] = ++m_;
    ++deg_in_[v];
  }
  int Head(int id_v) { return hd_[id_v]; }
  int Next(int id_e) { return e_[id_e].nxt; }
  int To(int id_e) { return e_[id_e].v; }
  long long& W(int id_e) { return e_[id_e].w; }
  int& Type(int id_e) { return e_[id_e].type; }
  int NumNode() { return n_; }
  long long WNode(int u) { return weight[u]; }

 private:
  struct Edge {
    int v, nxt;
    long long w;
    int type;
    Edge(int _v, int _nxt, long long _w, int _type)
        : v(_v), nxt(_nxt), w(_w), type(_type) {}
  };
  int n_;
  std::vector<int> hd_;
  long long weight[N];
  int m_;
  std::vector<Edge> e_;
  std::vector<bool> vis_;
  int deg_in_[N];
  int connected_num_;
} graph;
class EdgeBiconnection {
 public:
  void Init(int n, int m) {
    n_ = n;
    m_ = m;
    cnt_bicon = 0;
    for (int i = 1; i <= n; ++i) {
      id[i] = 0;
      w[i] = 0ll;
    }
    for (int i = 1; i <= m; ++i) {
      is_bridge[i] = false;
    }
    while (!sta.empty()) {
      sta.pop();
    }
  }
  bool Build(Graph& graph) {
    for (int i = 1; i <= n_; ++i) {
      if (!dfn[i]) {
        Dfs(graph, i, i, 0);
      }
    }
    return cnt_bicon == 1;
  }
  void SetRoot(int u) { root = id[u]; }
  long long Dp() {
    Dfs2(root, root);
    return std::max(dp[root][0], dp[root][1]);
  }
  int Id(int u) { return id[u]; }
  int NumNode() { return cnt_bicon; }
  int NodeSize(int id) { return bicons[id].size(); }

 private:
  void Dfs(Graph& graph, int u, int fa, int id_edge) {
    dfn[u] = ++dfs_time;
    low[u] = dfn[u];
    sta.push(u);
    for (int i = graph.Head(u); i; i = graph.Next(i)) {
      int v = graph.To(i);
      if (v != fa) {
        if (!dfn[v]) {
          ans.push_back({u, v});
          Dfs(graph, v, u, i);
          low[u] = std::min(low[u], low[v]);
        } else if (dfn[v] < dfn[u]) {
          ans.push_back({u, v});
          low[u] = std::min(low[u], dfn[v]);
        } else {
        }
      }
    }
    if (low[u] == dfn[u]) {
      ++cnt_bicon;
      bicons[cnt_bicon].clear();
      do {
        int tmp = sta.top();
        id[tmp] = cnt_bicon;
        bicons[cnt_bicon].push_back(tmp);
        w[cnt_bicon] += graph.WNode(tmp);
        sta.pop();
      } while (!sta.empty() && dfn[sta.top()] >= dfn[u]);
      is_bridge[(id_edge + 1) >> 1] = true;
    }
  }
  void Dfs2(int u, int f) {
    dp[u][1] = 0ll;
    dp[u][0] = graph_con.WNode(u);
    back[u] = bicons[u].size() > 1 ? true : false;
    long long sub_mx = 0ll;
    long long sub_sum = 0ll;
    bool back_sub = false;
    for (int i = graph_con.Head(u); i; i = graph_con.Next(i)) {
      int v = graph_con.To(i);
      if (v != f) {
        Dfs2(v, u);
        sub_mx = std::max(sub_mx, dp[v][0] - dp[v][1]);
        sub_sum += dp[v][1];
        back_sub |= back[v];
      }
    }
    if (back_sub) {
      back[u] = true;
      dp[u][1] = graph_con.WNode(u) + sub_sum;
    } else if (back[u]) {
      dp[u][1] = graph_con.WNode(u);
    } else {
      dp[u][1] = 0ll;
    }
    dp[u][0] += std::max(sub_sum, sub_mx + sub_sum);
  }
  int n_;
  int dfs_time;
  int dfn[N];
  int low[N];
  int id[N];
  std::stack<int> sta;
  int cnt_bicon;
  long long w[N];
  std::map<std::pair<int, int>, bool> ma;
  Graph graph_con;
  std::vector<int> bicons[N];
  int root;
  long long dp[N][2];
  bool back[N];
  int m_;
  bool is_bridge[M];
} edge_bicon;
int t;
int n, m;
int a[M];
int b[M];
int main() {
  scanf("%d%d", &n, &m);
  graph.Init(n);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &a[i], &b[i]);
    graph.Add(a[i], b[i]);
    graph.Add(b[i], a[i]);
  }
  edge_bicon.Init(n, m);
  if (edge_bicon.Build(graph)) {
    assert(ans.size() == m);
    for (size_t i = 0; i < ans.size(); ++i) {
      printf("%d %d\n", ans[i].first, ans[i].second);
    }
  } else {
    printf("0\n");
  }
  return 0;
}