#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <map>
//#include <iostream>
using namespace std;

typedef struct paar{
	int a, b;
}paar;
typedef struct kolm{
	paar p;
	int t;
}kolm;

struct vdp{
	bool operator()(paar x, paar y) const{
		if (x.a==y.a) return (x.b<y.b); return (x.a<y.a);
	}
};
struct vdk{
	bool operator()(kolm x, kolm y) const{
		if (x.t==y.t) {
			if (x.p.a==y.p.a) return (x.p.b<y.p.b); return (x.p.a<y.p.a);
		}
		return (x.t>y.t);
	}
};

int n,m;
paar alg,lopp;

map<paar,int,vdp> aeg;
priority_queue<kolm, vector<kolm>, vdk> pq;
set<int> serv[110];
map<paar,paar,vdp> parent;

void lisa(int a, int b, kolm k, int inc){
//	cout << a << " " << b << " | " << k.p.a << " " << k.p.b << endl;
	kolm uus;
	paar pp;
	pp.a=a; pp.b=b;
	if (aeg.find(pp)==aeg.end() || aeg[pp]>k.t+inc){
		aeg[pp]=k.t+inc;
		parent[pp]=k.p;
		uus.p=pp; uus.t=k.t+inc; pq.push(uus);
	}
}


int lahenda(){
	kolm tmp;
	tmp.t=0;
	aeg[alg]=0;
	tmp.p=alg;
	pq.push(tmp);

	while (true){
//		cout << pq.size() << endl;
		tmp=pq.top(); pq.pop();

//		cout << tmp.p.a << " " << tmp.p.b << endl;

		if ((tmp.p.a==lopp.a) && (tmp.p.b==lopp.b)) return tmp.t;

		set<int>::iterator it; it=serv[tmp.p.a].begin();
		while (it!=serv[tmp.p.a].end()){
//			cout << *it << endl << endl;
			if (serv[*it].find(tmp.p.b)!=serv[*it].end()) {
				lisa(*it,tmp.p.b,tmp,1);
			}
			set<int>::iterator it2; it2=serv[tmp.p.b].begin();
			while (it2!=serv[tmp.p.b].end()){
				if (serv[*it].find(*it2)!=serv[*it].end())
					if (!( (*it2==tmp.p.a)&&(*it==tmp.p.b) )) lisa(*it,*it2,tmp,2);
				it2++;
			}
			
			it++;
		}

		set<int>::iterator it2; it2=serv[tmp.p.b].begin();
			while (it2!=serv[tmp.p.b].end()){
				if (serv[tmp.p.a].find(*it2)!=serv[tmp.p.a].end()) lisa(tmp.p.a,*it2,tmp,1);
				it2++;
			}
		

	}
}
		

int main(){

	ifstream sis("kingdom.in");
	sis >> n >> m >> alg.a >> alg.b >> lopp.a >> lopp.b;
	for (int i=0; i<m; i++){
		int x,y;
		sis >> x >> y;
		serv[x].insert(y);
		serv[y].insert(x);
	}
	
	ofstream val("kingdom.out");
	val << lahenda();
	
//	cout << "ok" << endl;

	paar abi=lopp;
	vector<paar> tulem;
	while ((abi.a!=alg.a)|| (abi.b!=alg.b)){
		tulem.push_back(abi);
		abi=parent[abi];
	}
	tulem.push_back(alg);
	val << " " << tulem.size() << endl;
	for (int j=tulem.size()-1; j>=0; j--) val << tulem[j].a << " " << tulem[j].b << endl;


	return 0;
}