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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;



public class COVID {

	//	static int[] fac;
	//	static int mod=(int)1e9+7;


	static ArrayList<Integer>[] adjList;
	static int dfs_num[],dfs_low[],timer;
	static int mx=0,s;
	//static LinkedList<Integer> stack;
	static boolean[] vis;
	public static int dfs(int u) {
		vis[u]=true;
		int ans=1;
		for(int e:adjList[u]) {
			if(bridge.contains(e))continue;
			int v=u^edges[e][0]^edges[e][1];
			
			if(!vis[v])
				ans+=dfs(v);
		}
		return ans;
	}
	public static void Tarjan(int u,int p)
	{
//		stack.addLast(u);
		dfs_low[u]=dfs_num[u]=++timer;
		for(Integer e:adjList[u]) {
			if(e==p)continue;
			int v=u^edges[e][0]^edges[e][1];
			if(dfs_num[v]==0) {
				Tarjan(v,e);
				if(dfs_low[v]>dfs_num[u]) {
					edges[e][0]=v;
					edges[e][1]=u;
					bridge.add(e);

				}
				else {
					edges[e][0]=u;
					edges[e][1]=v;

				}
			}else {
				edges[e][0]=v;
				edges[e][1]=u;

			}
			dfs_low[u]=Math.min(dfs_low[u], dfs_low[v]);
		}

//		if(dfs_low[u]==dfs_num[u]) {
//			int c=0;
//			while(true) {
//				c++;
//				int x= stack.removeLast();
//				if(x==u)break;
//
//			}
//			if(c>mx) {
//				mx=c;
//				s=u;
//			}
//
//		}
	}



	static int[][] edges;

	static HashSet<Integer> bridge;
	public static void main(String[] args) throws Exception {

	Scanner	sc = new Scanner(System.in);
	PrintWriter	pw =new PrintWriter(System.out);
		int n=sc.nextInt();
		int m =sc.nextInt();
		bridge=new HashSet<>();
		adjList=new ArrayList[n];
		dfs_low=new int[n];
		dfs_num=new int[n];
		vis=new boolean[n];
	//	stack=new LinkedList();
		timer=0;
		for(int i=0;i<n;i++) {
			adjList[i]=new ArrayList();
		}
		edges=new int[m][2];
		for(int i=0;i<m;i++) {
			int u=sc.nextInt()-1;
			int v=sc.nextInt()-1;
			adjList[u].add(i);
			adjList[v].add(i);
			edges[i][0]=u;
			edges[i][1]=v;

		}

		Tarjan(0, -1);
		for(int i=0;i<n;i++) {
			if(dfs_low[i]==dfs_num[i]) {
				int c=dfs(i);
				if(c>mx) {
					mx=c;
					s=i;
				}
			}
		}
		Arrays.fill(dfs_low, 0);
		Arrays.fill(dfs_num, 0);
		timer=0;

		Tarjan(s, -1);
		pw.println(mx);
		for(int i=0;i<edges.length;i++)
			pw.println(1+edges[i][0]+" "+(1+edges[i][1]));


		pw.flush();
		pw.close();

	}

	//	static long gcd(long a, long b) {
	//		return (b==0)?a:gcd(b,a%b);
	//	}
	//	static long lcm(long a, long b) {
	//		return a/gcd(a,b)*b;
	//	}
	//	public static int log(int n , int base) {
	//		int ans=0;
	//		while(n+1>base) {
	//			ans++;
	//			n/=base;
	//		}
	//		return ans;
	//	}
	//	static long square(long l) {
	//		return l*l;
	//	}
	//	static int pow(int b,long e) {
	//		int ans=1;
	//		while(e>0) {
	//			if((e&1)==1)
	//				ans=(int)((ans*1l*b));
	//			e>>=1;{
	//
	//			}
	//			b=(int)((b*1l*b));
	//		}
	//		return ans;
	//	}
	//	static int powmod(int b,long e, int mod) {
	//		int ans=1;
	//		b%=mod;
	//		while(e>0) {
	//			if((e&1)==1)
	//				ans=(int)((ans*1l*b)%mod);
	//			e>>=1;
	//			b=(int)((b*1l*b)%mod);
	//		}
	//		return ans;
	//	}
	//	public static long add(long a, long b) {
	//		return (a+b)%mod;
	//	}
	//	public static long mul(long a, long b) {
	//		return ((a%mod)*(b%mod))%mod;
	//	}





	static class Pair implements Comparable<Pair>{
		int  x;int y;

		public Pair(int a,int b) {
			this.x=a;y=b;
		}



		public int compareTo(Pair o) {
			return (x==o.x)?((y>o.y)?1:(y==o.y)?0:-1):((x>o.x)?1:-1);
		}


		@Override


		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}






	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr=new long[n];
			for(int i=0;i<n;i++)
				arr[i]=nextLong();
			return arr;
		}
		public int[] nextIntArr(int n) throws IOException {
			int[] arr=new int[n];
			for(int i=0;i<n;i++)
				arr[i]=nextInt();
			return arr;
		}
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine()," ,");
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}


		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}