//usage: ./CutEdgesLinear <input_graph> <output_file>

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int n, m;
int* edges;
int* G; int* firstOut;

void create_adj();
void find_cut_edges();
int* cut_edges;
int n_cut_edges;
int n_cut_pairs;

int main(int n_args, char** args){
	FILE* fp = fopen(args[1], "r");
	fscanf(fp, "%d %d", &n, &m);
	edges = (int*)malloc(sizeof(int)*2*m);
	for(int i=0;i<m;i++){
		int x, y;
		fscanf(fp, "%d %d", &x, &y);
		edges[2*i]=x-1; edges[2*i+1]=y-1;
	}
	fclose(fp);

	create_adj();

	struct timeval begin, end;
   gettimeofday(&begin, 0);
	find_cut_edges();
	gettimeofday(&end, 0);
	long seconds = end.tv_sec - begin.tv_sec;
	long microseconds = end.tv_usec - begin.tv_usec;
	double elapsed = seconds + microseconds*1e-6;
	printf("Total time= %g\n", elapsed);

	fp = fopen(args[2], "w");
	fprintf(fp, "%d\n", n_cut_edges);
	for(int i=0;i<n_cut_edges;i++){
		fprintf(fp, "%d %d\n", cut_edges[2*i]+1, cut_edges[2*i+1]+1);
	}
	fprintf(fp, "%d\n", n_cut_pairs);
	fprintf(fp, "%lf\n", elapsed);

	fclose(fp);

	return 0;
}

void find_cut_edges(){
	cut_edges = (int*)malloc(sizeof(int)*(4*n-4));
	n_cut_edges = 0;

	int* dfs = (int*)malloc(sizeof(int)*n);
	int* idfs = (int*)malloc(sizeof(int)*n);
	int* p = (int*)malloc(sizeof(int)*n);
	int* l = (int*)malloc(sizeof(int)*n);
	int* low = (int*)malloc(sizeof(int)*n);
	int* currentChild = (int*)malloc(sizeof(int)*n);
	int* nextSibling = (int*)malloc(sizeof(int)*n);
	int* prevSibling = (int*)malloc(sizeof(int)*n);
	int* L = (int*)malloc(sizeof(int)*n);
	int* R = (int*)malloc(sizeof(int)*n);
	int* M = (int*)malloc(sizeof(int)*n);
	int* nextM = (int*)malloc(sizeof(int)*n);
	int* bCount = (int*)malloc(sizeof(int)*n);

	int* stack = (int*)malloc(sizeof(int)*n);
	int* temp_out = (int*)malloc(sizeof(int)*n);

	for(int i=0;i<n;i++){
		dfs[i]=-1; l[i]=i; low[i]=i; currentChild[i]=-1; bCount[i]=0; nextSibling[i]=-1;prevSibling[i]=-1;
	}

	//perform DFS
	int Nr=0;
	dfs[0]=Nr; idfs[Nr++]=0;
	stack[0]=0; temp_out[0]=firstOut[0];
	int SP=0;
	while(SP!=-1){
		int v=stack[SP];
		char down=0;
		for(int i=temp_out[SP];i<firstOut[v+1];i++){
			int u=G[i];
			if(dfs[u]==-1){
				dfs[u]=Nr; idfs[Nr++]=u; p[u]=v;
				if(currentChild[v]!=-1){
					nextSibling[currentChild[v]]=u;
					prevSibling[u]=currentChild[v];
				}
				currentChild[v]=u;
				stack[SP+1]=u; temp_out[SP+1]=firstOut[u]; temp_out[SP]=i;
				down=1; break;
			}
			if(dfs[u]<dfs[v] && u!=p[v]){
				if(dfs[u]<dfs[l[v]]){ l[v]=u; }
				if(dfs[u]<dfs[low[v]]){ low[v]=u; }
				bCount[v]++; bCount[u]--;
			} else if(v==p[u]){
				if(dfs[low[u]]<dfs[low[v]]){ low[v]=low[u]; }
				bCount[v]+=bCount[u];
			}
		}
		if(down){ SP++;continue; }
		SP--;
	}

	//initialize all L and R
	for(int v=0;v<n;v++){ L[v]=-1; }
	for(int i=1;i<n;i++){
		int u=idfs[i];
		if(dfs[low[u]]<dfs[p[u]]){
			if(L[p[u]]==-1){
				L[p[u]]=u; R[p[u]]=u;
			} else{
				R[p[u]]=u;
			}
		}
	}

	//calculate M and nextM
	for(int v=0;v<n;v++){ nextM[v]=-1; }
	for(int i=n-1;i>0;i--){
		int v=idfs[i];
		if(l[v]!=v){ M[v]=v;continue; }
		if(L[v]!=R[v]){ M[v]=v;continue; }
		int c=L[v];
		int m=M[c];
		while(1){
			if(dfs[l[m]]<i){ M[v]=m;break; }
			while(dfs[low[L[m]]]>=i){ L[m]=nextSibling[L[m]]; }
			while(dfs[low[R[m]]]>=i){ R[m]=prevSibling[R[m]]; }
			if(L[m]!=R[m]){ M[v]=m;break; }
			c=L[m];
			m=M[c];
		}
		nextM[c]=v;
	}

	char* tree_edge_is_cut_edge = (char*)malloc(sizeof(char)*n);
	char* back_edge_is_cut_edge = (char*)malloc(sizeof(char)*n);

	for(int i=0;i<n;i++){
		tree_edge_is_cut_edge[i]=0; back_edge_is_cut_edge[i]=0;
	}

	//find cut-edges
	for(int v=1;v<n;v++){
		if(bCount[v]==1){
			back_edge_is_cut_edge[M[v]]=1;
			tree_edge_is_cut_edge[v]=1;
		}
		int next=nextM[v];
		if(next!=-1 && bCount[v]==bCount[next]){
			tree_edge_is_cut_edge[v]=1;
			tree_edge_is_cut_edge[next]=1;
		}
	}

	//count cut-pairs
	n_cut_pairs=0;
	for(int v=1;v<n;v++){
		if(bCount[v]==1){
			n_cut_pairs++;
		}
	}
	for(int v=1;v<n;v++){
		if(v!=M[v]){ continue; }
		int u=v;
		while(u!=-1){
			int next=nextM[u];
			if(next==-1){ break; }
			int n_edges=0;
			int b=bCount[u];
			while(b==bCount[next]){
				n_edges++;
				next=nextM[next];
				if(next==-1){ break; }
			}
			n_cut_pairs+=(n_edges*(n_edges+1))/2;
			u=next;
		}
	}

	for(int v=1;v<n;v++){
		if(tree_edge_is_cut_edge[v]){
			cut_edges[2*n_cut_edges]=v;
			cut_edges[2*n_cut_edges+1]=p[v];
			n_cut_edges++;
		}
		if(back_edge_is_cut_edge[v]){
			cut_edges[2*n_cut_edges]=v;
			cut_edges[2*n_cut_edges+1]=low[v];
			n_cut_edges++;
		}
	}
}

void create_adj(){
	G = (int*)malloc(sizeof(int)*4*m);
	firstOut = (int*)malloc(sizeof(int)*(n+1));
	for(int i=0;i<=n;i++){ firstOut[i]=0; }
	for(int i=0;i<m;i++){ firstOut[edges[2*i]+1]++; firstOut[edges[2*i+1]+1]++; }
	int* nextOut = (int*)malloc(sizeof(int)*(n+1));
	nextOut[0]=0;
	for(int i=1;i<=n;i++){ firstOut[i]+=firstOut[i-1]; nextOut[i]=firstOut[i]; }
	for(int i=0;i<m;i++){
		int x=edges[2*i]; int y=edges[2*i+1];
		G[nextOut[x]++]=y;
		G[nextOut[y]++]=x;
	}
}