#include <stdio.h>

#define KK 110
#define NN 12100
#define MM 1024
#define SS 1024

struct REB {
	int a;
	int w;
	REB *p;
};

struct POINT {
	int x,y;
};

FILE *fi, *fo;
REB *swap;
int iswap=SS;
int n,m,k;
int a[KK][KK];
REB *g[NN];
int used[NN];
int r[NN];
int r2[NN];
int d[NN];
int a1,b1,a2,b2;
POINT pp[MM];
int q[NN];

int min(int a, int b) { return (a<b)?a:b; }
int max(int a, int b) { return (a>b)?a:b; }

REB *getnew() {
	if(iswap>=SS) {
		swap=new REB[SS];
		iswap=0;
	}
	return &swap[iswap++];
}

POINT makepoint(int x, int y) {
	POINT p;
	p.x=x;
	p.y=y;
	return p;
}

int pack(POINT p) {
	if(p.y>p.x) {
		return p.x*(k-1)+p.y-1;
	} else {
		return p.x*(k-1)+p.y;
	}
}

POINT unpack(int v) {
	POINT res;
	res.x=v/(k-1);
	res.y=v%(k-1);
	if(res.y>=res.x) res.y++;
	return res;
}

void addreb(int x, int y, int w) {
	REB *t;
	t=getnew();
	t->a=y;
	t->p=g[x];
	t->w=w;
	g[x]=t;
}

void bfs(int st) {
	int b1,b2,e;
	int i;
	int c;
	REB *t;
	for(i=0;i<n;i++) {
		used[i]=0;
		r[i]=-1;
		d[i]=-1;
		r2[i]=-1;
	}
	q[0]=st;
	r[st]=0;
	r2[st]=0;
	used[st]=1;
	e=1;
	b1=0;
	b2=0;
	while((b1<e)||(b2<e)) {
		while(b1<e) {
			if(b1>0) {
				if(r[q[b1-1]]<r[q[b1]]) {
					if(b1>b2) 
						break;
				}
			}
			c=q[b1++];
			for(t=g[c];t!=NULL;t=t->p) {
				if(t->w==1) {
					if(!used[t->a]) {
						q[e]=t->a;
						used[t->a]=1;
						r[q[e]]=r[c]+1;
						r2[q[e]]=r2[c]+1;
						d[q[e]]=c;
						e++;
					}
				}
			}
		}
		while(b2<=b1) {
			c=q[b2++];
			for(t=g[c];t!=NULL;t=t->p) {
				if(t->w==2) {
					if(!used[t->a]) {
						q[e]=t->a;
						r[q[e]]=r[c]+2;
						used[t->a]=1;
						r2[q[e]]=r2[c]+1;
						d[q[e]]=c;
						e++;
					}
				}
			}
		}
	}
}

void wr(int v) {
	POINT t;
	if(d[v]>=0)
		wr(d[v]);
	t=unpack(v);
	fprintf(fo,"%d %d\n",t.x+1,t.y+1);
}

int main() {
	int i,j,l;
	int xx,yy;
	fi=fopen("kingdom.in","rt");
	fo=fopen("kingdom.out","wt");

	for(i=0;i<KK;i++) {
		for(j=0;j<KK;j++) {
			a[i][j]=0;
		}
	}
	for(i=0;i<NN;i++) {
		g[i]=NULL;
	}

	fscanf(fi,"%d%d",&k,&m);
	fscanf(fi,"%d%d%d%d",&a1,&b1,&a2,&b2);
	a1--; b1--; a2--; b2--;
	for(i=0;i<m;i++) {
		fscanf(fi,"%d%d",&xx,&yy);
		xx--; yy--;
		pp[i].x=xx;
		pp[i].y=yy;
		a[xx][yy]++;
		if(xx!=yy)
			a[yy][xx]++;
	}
	for(i=0;i<k;i++) {
		for(j=0;j<k;j++) {
			if(i!=j) {
				for(l=0;l<k;l++) {
					if((l!=i)&&(l!=j)&&(a[i][l])&&(a[j][l])) {
						addreb(pack(makepoint(i,j)),pack(makepoint(l,j)),1);
					}
					if((l!=i)&&(l!=j)&&(a[j][l])&&(a[i][l])) {
						addreb(pack(makepoint(i,j)),pack(makepoint(i,l)),1);
					}
				}
			}
		}
	}
	for(i=0;i<m;i++) {
		for(j=0;j<m;j++) {
			if(i==j) continue;
			if((pp[i].x!=pp[j].x)&&(pp[i].y!=pp[j].y)&&(a[pp[i].y][pp[j].y])) {
				addreb(pack(makepoint(pp[i].x,pp[j].x)),pack(makepoint(pp[i].y,pp[j].y)),2);
			}
			if((pp[i].x!=pp[j].y)&&(pp[i].y!=pp[j].x)&&(a[pp[i].y][pp[j].x])) {
				addreb(pack(makepoint(pp[i].x,pp[j].y)),pack(makepoint(pp[i].y,pp[j].x)),2);
			}
		}
	}
	n=k*(k-1);
	bfs(pack(makepoint(a1,b1)));

	//If no solution?????

	j=pack(makepoint(a2,b2));
	fprintf(fo,"%d %d\n",r[j],r2[j]+1);
	wr(j);

	fclose(fi);
	fclose(fo);
	return 0;
}