#include <stdio.h>

struct tp {
	int		x,y;
};

int main() {
	FILE	*FI, *FO;
	FI=fopen("kingdom.in","rt");
	FO=fopen("kingdom.out","wt");
	int		n, m, a1, b1, a2, b2;
	int		x, y;
	long	cnt[128][128];
	char	port[128][128];
	char	mask[128][128];
	tp		prev[128][128];
	int		i, j;
	fscanf(FI,"%d %d %d %d %d %d",&n,&m,&a1,&b1,&a2,&b2);
	a1--; b1--; a2--; b2--;
	for (i=0; i<n; i++) for (j=0; j<n; j++) { cnt[i][j]=-1; port[i][j]=0; mask[i][j]=0; }
	for (i=0; i<m; i++) {
		fscanf(FI,"%d %d",&x,&y);
		x--; y--;
		port[y][x]=port[x][y]=1;
	}
	fclose(FI);

	cnt[a1][b1]=0;
	int		si, sj, min;
	while (1) {
		min=-1;
		for (i=0; i<n; i++)
			for (j=0; j<n; j++) if (!mask[i][j] && cnt[i][j]!=-1) {
				if (min==-1 || (cnt[i][j]<min)) {
					si=i;
					sj=j;
					min=cnt[i][j];
				}
			}
		if (min<0) break;
		mask[si][sj]=1;
		for (i=0; i<n; i++) if (port[si][i] && port[i][sj]) {
			if (cnt[i][sj]==-1 || (cnt[i][sj]>cnt[si][sj]+1)) {
				cnt[i][sj]=cnt[si][sj]+1;
				prev[i][sj].x=si;
				prev[i][sj].y=sj;
			}
		}
		for (i=0; i<n; i++) if (port[sj][i] && port[i][si]) {
			if (cnt[si][i]==-1 || (cnt[si][i]>cnt[si][sj]+1)) {
				cnt[si][i]=cnt[si][sj]+1;
				prev[si][i].x=si;
				prev[si][i].y=sj;
			}
		}
		for (i=0; i<n; i++) if (port[si][i]) {
			for (j=0; j<n; j++) if (port[sj][j] && port[i][j] && !(i==sj && j==si)) {
				if (cnt[i][j]==-1 || (cnt[i][j]>cnt[si][sj]+2)) {
					cnt[i][j]=cnt[si][sj]+2;
					prev[i][j].x=si;
					prev[i][j].y=sj;
				}
			}
		}
	}


	tp		path[10000];
	long	lpath=0;
	int		px, py;
	if (cnt[a2][b2]!=-1) {
		px=a2;
		py=b2;
		path[lpath].x=px;
		path[lpath].y=py;
		lpath++;
		while (!(px==a1 && py==b1)) {
			path[lpath].x=prev[px][py].x;
			path[lpath].y=prev[px][py].y;
			px=path[lpath].x;
			py=path[lpath].y;
			lpath++;
		}
	}

	if (cnt[a2][b2]==-1) {
		fprintf(FO,"0 0\n");
		fclose(FO);
		return 0;
	}
	fprintf(FO,"%d %d\n",cnt[a2][b2],lpath);
	for (i=lpath-1; i>=0; i--) 
		fprintf(FO,"%d %d\n",path[i].x+1,path[i].y+1);
	fclose(FO);
	return 0;
}