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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskF solver = new TaskF();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskF {
    QuickWriter out;
    int n;
    int m;
    BlockableBidirectionalGraph graph;
    int[] answer;
    int[] dfn;
    int[] low;
    int[] ce;
    int ceCnt;
    boolean[] visited;
    boolean[] edgeD;
    boolean[] dfsVisited;
    int[] bfs;
    int[] marker;
    int[] compSize;
    int compCnt;
    IntEdgeWeightedDirectedGraph subGraph;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      this.out = out;
      n = in.nextInt();
      m = in.nextInt();
      graph = new BlockableBidirectionalGraph(n, m);
      for (int i = 0; i < m; ++i) {
        graph.add(in.nextInt() - 1, in.nextInt() - 1);
      }
      answer = new int[m];
      calcCutEdge();
      handleComponent();
      calcCED();
      for (int i = 0; i < m; ++i) {
        int idx = answer[i];
        out.println(graph.fromIdx[idx] + 1, graph.toIdx[idx] + 1);
      }
    }

    void calcCutEdge() {
      dfn = new int[n];
      low = new int[n];
      ce = new int[m];
      ceCnt = CutEdge.calc(graph, ce, dfn, low);
      for (int i = 0; i < ceCnt; ++i) graph.block(ce[i]);
    }

    void handleComponent() {
      visited = new boolean[n];
      bfs = new int[n];
      marker = new int[n];
      compCnt = 0;
      compSize = new int[n];
      edgeD = new boolean[m << 1];
      dfsVisited = new boolean[n];
      for (int i = 0; i < n; ++i)
        if (!visited[i]) {
          int cnt = BfsOrder.calc(graph, i, bfs, visited);
          for (int j = 0; j < cnt; ++j) {
            marker[bfs[j]] = compCnt;
          }
          compSize[compCnt++] = cnt;
          dfsComponent(bfs[0]);
        }
    }

    void dfsComponent(int u) {
      dfsVisited[u] = true;
      for (int edgeIdx = graph.lastOut[u]; edgeIdx >= 0; edgeIdx = graph.nextOut[edgeIdx]) {
        if (!edgeD[edgeIdx] && !graph.blocked(edgeIdx)) {
          int v = graph.toIdx[edgeIdx];
          answer[edgeIdx >> 1] = edgeIdx;
          edgeD[edgeIdx] = edgeD[edgeIdx ^ 1] = true;
          if (!dfsVisited[v]) dfsComponent(v);
        }
      }
    }

    void calcCED() {
      subGraph = new IntEdgeWeightedDirectedGraph(compCnt, ceCnt << 1);
      for (int i = 0; i < ceCnt; ++i) {
        int idx = ce[i];
        int fromIdx = marker[graph.fromIdx[idx]];
        int toIdx = marker[graph.toIdx[idx]];
        subGraph.add(fromIdx, toIdx, idx);
        subGraph.add(toIdx, fromIdx, idx ^ 1);
      }
      int res = IntArrayUtils.max(compSize, 0, compCnt);
      out.println(res);
      int resIdx = IntArrayUtils.find(compSize, 0, compCnt, res);
      Arrays.fill(visited, 0, compCnt, false);
      dfsTree(resIdx);
    }

    void dfsTree(int u) {
      visited[u] = true;
      for (int edgeIdx = subGraph.lastOut[u]; edgeIdx >= 0; edgeIdx = subGraph.nextOut[edgeIdx]) {
        int v = subGraph.toIdx[edgeIdx];
        if (visited[v]) continue;
        dfsTree(v);
        int idx = subGraph.edgeWeights[edgeIdx ^ 1];
        answer[idx >> 1] = idx;
      }
    }

  }

  static interface BlockableBidirectionalGraphInterface extends Blockable, BidirectionalGraphInterface {
  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static class BlockableBidirectionalGraph extends BlockableDirectedGraph implements BlockableBidirectionalGraphInterface {
    public BlockableBidirectionalGraph(int vertexCapacity, int edgeCapacity) {
      super(vertexCapacity, edgeCapacity << 1);
    }


    public void add(int fromIdx, int toIdx) {
      super.add(fromIdx, toIdx);
      super.add(toIdx, fromIdx);
    }


    public void block(int edgeIdx) {
      super.block(edgeIdx);
      super.block(edgeIdx ^ 1);
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' '
          || c == '\n'
          || c == '\r'
          || c == '\t'
          || c < 0;
    }

  }

  static interface DirectedGraphInterface {
    int vertexCnt();

    int toIdx(int edgeIdx);

    int lastOut(int nodeIdx);

    int nextOut(int edgeIdx);

  }

  static interface BlockableDirectedGraphInterface extends DirectedGraphInterface, Blockable {
  }

  static class BfsOrder {
    public static int calc(DirectedGraphInterface graph, int startIdx, int[] bfs, boolean[] visited) {
      if (visited[startIdx]) return 0;
      BlockableDirectedGraphInterface blockableGraph = null;
      if (graph instanceof Blockable) {
        blockableGraph = (BlockableDirectedGraphInterface) graph;
      }
      visited[startIdx] = true;
      int res = 0;
      bfs[res++] = startIdx;
      for (int i = 0; i < res; ++i) {
        int u = bfs[i];
        for (int edgeIdx = graph.lastOut(u); edgeIdx >= 0; edgeIdx = graph.nextOut(edgeIdx)) {
          if (blockableGraph == null || !blockableGraph.blocked(edgeIdx)) {
            int v = graph.toIdx(edgeIdx);
            if (!visited[v]) {
              visited[v] = true;
              bfs[res++] = v;
            }
          }
        }
      }
      return res;
    }

  }

  static class CutEdge {
    public static int calc(BidirectionalGraphInterface graph, int[] cutEdges, int[] dfn, int[] low) {
      int n = graph.vertexCnt();
      Arrays.fill(dfn, 0, n, 0);
      Arrays.fill(low, 0, n, 0);
      int res = 0;
      for (int i = 0; i < n; ++i)
        if (dfn[i] == 0) {
          res = tarjan(i, 1, -1, graph, cutEdges, res, dfn, low);
        }
      return res;
    }

    private static int tarjan(
        int u,
        int dfs,
        int prevEdgeIdx,
        BidirectionalGraphInterface graph,
        int[] cutEdges,
        int res,
        int[] dfn,
        int[] low) {

      dfn[u] = low[u] = dfs;
      for (int edgeIdx = graph.lastOut(u); edgeIdx >= 0; edgeIdx = graph.nextOut(edgeIdx)) {
        int v = graph.toIdx(edgeIdx);
        if (dfn[v] == 0) {
          res = tarjan(v, dfs + 1, edgeIdx, graph, cutEdges, res, dfn, low);
          low[u] = Math.min(low[u], low[v]);
          if (low[v] > dfn[u]) cutEdges[res++] = edgeIdx;
        } else if (prevEdgeIdx < 0 || (prevEdgeIdx ^ 1) != edgeIdx) {
          low[u] = Math.min(low[u], dfn[v]);
        }
      }
      return res;
    }

  }

  static class IntArrayUtils {
    public static int max(int[] values, int fromIdx, int toIdx) {
      int res = Integer.MIN_VALUE;
      for (int i = fromIdx; i < toIdx; ++i) {
        if (res < values[i]) res = values[i];
      }
      return res;
    }

    public static int find(int[] values, int fromIdx, int toIdx, int value) {
      for (int i = fromIdx; i < toIdx; ++i) {
        if (values[i] == value) return i;
      }
      return -1;
    }

  }

  static interface BidirectionalGraphInterface extends DirectedGraphInterface {
  }

  static interface IntEdgeWeightedDirectedGraphInterface extends IntEdgeWeighted, DirectedGraphInterface {
  }

  static interface Blockable {
    boolean blocked(int edgeIdx);

  }

  static abstract class AbstractDirectedGraph implements DirectedGraphInterface {
    public int vertexCnt;
    public int currentEdgeCnt;
    public int[] fromIdx;
    public int[] toIdx;
    public int[] nextIn;
    public int[] nextOut;
    public int[] lastIn;
    public int[] lastOut;
    public int[] inDegree;
    public int[] outDegree;

    public abstract void createSubclass(int vertexCapacity, int edgeCapacity);

    public abstract void initSubclass(int vertexCnt);

    public AbstractDirectedGraph(int vertexCapacity, int edgeCapacity) {
      this(vertexCapacity, edgeCapacity, true);
    }

    public AbstractDirectedGraph(int vertexCapacity, int edgeCapacity, boolean initialize) {
      fromIdx = new int[edgeCapacity];
      toIdx = new int[edgeCapacity];
      lastIn = new int[vertexCapacity];
      lastOut = new int[vertexCapacity];
      nextIn = new int[edgeCapacity];
      nextOut = new int[edgeCapacity];
      inDegree = new int[vertexCapacity];
      outDegree = new int[vertexCapacity];
      createSubclass(vertexCapacity, edgeCapacity);
      if (initialize) init(vertexCapacity);
    }


    public void init(int vertexCnt) {
      this.vertexCnt = vertexCnt;
      currentEdgeCnt = 0;
      Arrays.fill(inDegree, 0, vertexCnt, 0);
      Arrays.fill(outDegree, 0, vertexCnt, 0);
      Arrays.fill(lastIn, 0, vertexCnt, -1);
      Arrays.fill(lastOut, 0, vertexCnt, -1);
      initSubclass(vertexCnt);
    }


    public void add(int fromIdx, int toIdx) {
      this.fromIdx[currentEdgeCnt] = fromIdx;
      this.toIdx[currentEdgeCnt] = toIdx;
      ++outDegree[fromIdx];
      ++inDegree[toIdx];
      nextOut[currentEdgeCnt] = lastOut[fromIdx];
      lastOut[fromIdx] = currentEdgeCnt;
      nextIn[currentEdgeCnt] = lastIn[toIdx];
      lastIn[toIdx] = currentEdgeCnt;
      ++currentEdgeCnt;
    }


    public int vertexCnt() {
      return vertexCnt;
    }


    public int toIdx(int edgeIdx) {
      return toIdx[edgeIdx];
    }


    public int lastOut(int nodeIdx) {
      return lastOut[nodeIdx];
    }


    public int nextOut(int edgeIdx) {
      return nextOut[edgeIdx];
    }

  }

  static class IntEdgeWeightedDirectedGraph extends AbstractDirectedGraph implements IntEdgeWeightedDirectedGraphInterface {
    public int[] edgeWeights;

    public IntEdgeWeightedDirectedGraph(int vertexCapacity, int edgeCapacity) {
      super(vertexCapacity, edgeCapacity);
    }


    public void createSubclass(int vertexCapacity, int edgeCapacity) {
      edgeWeights = new int[edgeCapacity];
    }


    public void initSubclass(int vertexCnt) {
    }


    public void add(int fromIdx, int toIdx) {
      throw new UnsupportedOperationException();
    }


    public void add(int fromIdx, int toIdx, int weight) {
      edgeWeights[currentEdgeCnt] = weight;
      super.add(fromIdx, toIdx);
    }

  }

  static interface IntEdgeWeighted {
  }

  static class BlockableDirectedGraph extends AbstractDirectedGraph implements BlockableDirectedGraphInterface {
    public boolean[] blocked;

    public BlockableDirectedGraph(int vertexCapacity, int edgeCapacity) {
      super(vertexCapacity, edgeCapacity);
    }


    public void createSubclass(int vertexCapacity, int edgeCapacity) {
      blocked = new boolean[edgeCapacity];
    }


    public void initSubclass(int vertexCnt) {
    }


    public void add(int fromIdx, int toIdx) {
      blocked[currentEdgeCnt] = false;
      super.add(fromIdx, toIdx);
    }


    public void block(int edgeIdx) {
      blocked[edgeIdx] = true;
      blocked[edgeIdx ^ 1] = true;
    }


    public boolean blocked(int edgeIdx) {
      return blocked[edgeIdx];
    }

  }
}