#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; template struct Dijkstra{ struct Edge{ int to; T cost; Edge(int to,T cost):to(to),cost(cost){} bool operator<(const Edge &o)const{return cost>o.cost;} }; const T inf = (numeric_limits::max())/2;//infを設定する vector> G; vector ds; vector bs; Dijkstra(int n):G(n){} void add_edge(int u,int v,T c){ G[u].push_back(Edge(v,c)); } void build(int s){ int n=G.size(); ds.assign(n,inf); bs.assign(n,-1); priority_queue pq; ds[s]=0; pq.emplace(s,ds[s]); while(!pq.empty()){ auto p=pq.top();pq.pop(); int v=p.to; if(ds[v]ds[v]+e.cost){ ds[e.to]=ds[v]+e.cost; bs[e.to]=v; pq.emplace(e.to,ds[e.to]); } } } } T operator[](int k){return ds[k];} vector restore(int to){ vector res; if(bs[to]<0) return res; while(~to) res.emplace_back(to),to=bs[to]; reverse(res.begin(),res.end()); return res; } }; int n,m;ll p; int s,g; void solve(){ cin >> n >> m >> p; cin >> s >> g;s--;g--; Dijkstra dij1(2*n),dij2(2*n); rep(i,m){ int a,b;cin >> a >> b;a--;b--; rep(j,2) dij1.add_edge(2*a+j,2*b+1-j,1); rep(j,2) dij2.add_edge(2*a+j,2*b+1-j,1); rep(j,2) dij1.add_edge(2*b+j,2*a+1-j,1); rep(j,2) dij2.add_edge(2*b+j,2*a+1-j,1); } dij1.build(2*s);dij2.build(2*g+p%2); vector ans={}; rep(i,n){ // cout << i << " " << dij1[2*i] << " " << dij1[2*i+1] << endl; // cout << i << " " << dij2[2*i] << " " << dij2[2*i+1] << endl; ll mi1=dij1[2*i]+dij2[2*i],mi2=dij1[2*i+1]+dij2[2*i+1]; if(min(mi1,mi2)<=p){ ans.push_back(i+1); } } if(ans.empty()){ cout << -1 << endl; return; } cout << ans.size() << endl; rep(i,ans.size()){ cout << ans[i] << endl; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }