Problem: Berland is a tourist country! At least, it can become such — the government of Berland is confident about this. 

There are n cities in Berland, some pairs of which are connected by two-ways roads. Each road connects two different cities. In Berland there are no roads which connect the same pair of cities. It is possible to get from any city to any other city using given two-ways roads. 

According to the reform each road will become one-way. It will be oriented to one of two directions.

To maximize the tourist attraction of Berland, after the reform for each city i the value ri will be calculated. It will equal to the number of cities x for which there is an oriented path from the city i to the city x. In other words, ri will equal the number of cities which can be reached from the city i by roads. 

The government is sure that tourist's attention will be focused on the minimum value of ri.

Help the government of Berland make the reform to maximize the minimum of ri.

Input

The first line contains two integers n, m (2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000) — the number of cities and the number of roads. 

The next m lines describe roads in Berland: the j-th of them contains two integers uj and vj (1 ≤ uj, vj ≤ n, uj ≠ vj), where uj and vj are the numbers of cities which are connected by the j-th road.

The cities are numbered from 1 to n. It is guaranteed that it is possible to get from any city to any other by following two-ways roads. In Berland there are no roads which connect the same pair of cities. 

Output

In the first line print single integer — the maximum possible value min1 ≤ i ≤ n{ri} after the orientation of roads. 

The next m lines must contain the description of roads after the orientation: the j-th of them must contain two integers uj, vj, it means that the j-th road will be directed from the city uj to the city vj. Print roads in the same order as they are given in the input data. 

Example

Input

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


Output

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

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

public class F {
  private static class Task {
    long N;
    TreeMap<Long, int[]> direction = new TreeMap<>();
    ArrayList<ArrayList<Integer>> graph;

    void disconnectedDfs(int v, int p, boolean[] vis) {
      vis[v] = true;
      for (int u : graph.get(v)) {
        if (u == p) continue;
        if (direction.containsKey(edgeValue(u, v))) continue;
        direction.put(edgeValue(u, v), new int[]{v, u});
        if (!vis[u]) {
          disconnectedDfs(u, v, vis);
        }
      }
    }

    void superDfs(int v, int p, int[] ord) {
      for (int u : graph.get(v)) {
        if (u == p) continue;
        ord[u] = ord[v] + 1;//v <- u
        superDfs(u, v, ord);
      }
    }

    void solve(FastScanner in, PrintWriter out) throws Exception {
      N = in.nextInt();
      int M = in.nextInt();
      int[][] edges = new int[2][M];
      graph = new ArrayList<>();
      for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
      for (int i = 0; i < M; i++) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        graph.get(u).add(v);
        graph.get(v).add(u);
        edges[0][i] = u;
        edges[1][i] = v;
      }

      int k;
      int[] cmp;
      ArrayList<int[]> bridges;
      {
        BiconnectedComponents bic = new BiconnectedComponents(graph);
        k = bic.k;
        cmp = bic.cmp;
        bridges = bic.bridges;
      }
      for (int i = 0; i < N; i++) graph.get(i).clear();

      int[] sizes = new int[k];
      for (int c : cmp) sizes[c]++;
      int maxSize = 0;
      int maxComponentId = 0;
      for (int i = 0; i < sizes.length; i++)
        if (maxSize < sizes[i]) {
          maxSize = sizes[i];
          maxComponentId = i;
        }

      for (ArrayList<Integer> g : graph) g.clear();

      for (int[] bridge : bridges) {
        int u = bridge[0];
        int v = bridge[1];
        graph.get(cmp[u]).add(cmp[v]);
        graph.get(cmp[v]).add(cmp[u]);
      }
      int[] ord = new int[k];
      superDfs(maxComponentId, -1, ord);
      for (ArrayList<Integer> g : graph) g.clear();

      for (int[] bridge : bridges) {
        int u = bridge[0];
        int v = bridge[1];
        if (ord[cmp[v]] < ord[cmp[u]]) {
          //u->v
          direction.put(edgeValue(u, v), new int[]{u, v});
        } else {
          //v->u
          direction.put(edgeValue(u, v), new int[]{v, u});
        }
      }

      for (int i = 0; i < M; i++) {
        if (!direction.containsKey(edgeValue(edges[0][i], edges[1][i]))) {
          graph.get(edges[0][i]).add(edges[1][i]);
          graph.get(edges[1][i]).add(edges[0][i]);
        }
      }

      boolean[] vis = new boolean[(int) N];
      for (int i = 0; i < N; i++) {
        if (!vis[i]) disconnectedDfs(i, -1, vis);
      }

      out.println(maxSize);
      for (int i = 0; i < M; i++) {
        int[] vu = direction.get(edgeValue(edges[0][i], edges[1][i]));
        out.println((vu[0] + 1) + " " + (vu[1] + 1));
      }

    }

    long edgeValue(int u, int v) {
      return N * Math.min(u, v) + Math.max(u, v);
    }

    class BiconnectedComponents {

      private int[] order;
      private ArrayDeque<Integer> stack = new ArrayDeque<>();
      private ArrayDeque<Integer> path = new ArrayDeque<>();
      private boolean[] inStack;
      private int idx;
      private int k;
      private final ArrayList<ArrayList<Integer>> G;

      public ArrayList<int[]> bridges = new ArrayList<>();
      public int[] cmp;

      BiconnectedComponents(ArrayList<ArrayList<Integer>> g) {
        int n = g.size();
        this.G = g;
        idx = 0;
        k = 0;
        order = new int[n];
        Arrays.fill(order, -1);
        inStack = new boolean[n];
        cmp = new int[n];

        for (int v = 0; v < n; v++) {
          if (order[v] == -1) {
            dfs(v, n);

            // [v, N] が追加されてしまっているので削除
            bridges.remove(bridges.size() - 1);
          }
        }
      }

      private void dfs(int v, int p) {
        order[v] = idx++;
        stack.addLast(v);
        inStack[v] = true;
        path.addLast(v);
        for (Integer to : G.get(v)) {
          if (to == p) continue;

          if (order[to] == -1)
            dfs(to, v);
          else if (inStack[to])
            while (order[path.peekLast()] > order[to]) path.pollLast();
        }

        if (v == path.peekLast()) {
          bridges.add(new int[]{p, v});
          while (true) {
            int w = stack.pollLast();
            inStack[w] = false;
            cmp[w] = k;
            if (v == w) break;
          }
          path.pollLast();
          ++k;
        }
      }
    }

  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) throws Exception {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}