#include "bits/stdc++.h" using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)n; ++i) #define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i) #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i) #define ALL(a) a.begin(), a.end() #define IN(a, x, b) (a <= x && x < b) templateistream&operator >>(istream&is,vector&vec){for(T&x:vec)is>>x;return is;} templateinline void out(T t){cout << t << "\n";} templateinline void out(T t,Ts... ts){cout << t << " ";out(ts...);} templateinline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;} templateinline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;} constexpr int INF = 1e18; signed main(){ int N, M, P, S, G; cin >> N >> M >> P >> S >> G; --S; --G; vector>g(N); REP(i, M) { int a, b; cin >> a >> b; --a; --b; g[a].emplace_back(b); g[b].emplace_back(a); } int isBiparititeGraph = 1; auto BiparititeGraph = [&](vector>&g){ vectorcol(g.size(),-1); auto dfs = [&](auto&&f,int now,int par,int bit) -> void{ col[now] = bit; for(auto e:g[now]){ if(col[e] != -1){ if(col[e] == (bit ^ 1))continue; else{ isBiparititeGraph = 0; } }else{ f(f,e,now,bit ^ 1); } } }; REP(i,g.size()){ if(col[i] == -1){ dfs(dfs,i,-1,0); } } return col; }; auto col = BiparititeGraph(g); //out(isBiparititeGraph, col[S], col[G]); if((isBiparititeGraph && (P % 2 != (col[G] != col[S])))) { out(-1); return 0; } auto f = [&](int start) { vectordist(N, INF); dist[start] = 0; priority_queue, vector>, greater>>que; que.push({dist[start], start}); while(que.size()) { auto[cost, now] = que.top(); que.pop(); if(dist[now] != cost) continue; for(auto e: g[now]) { if(CHMIN(dist[e], cost + 1)) { que.push({dist[e], e}); } } } return dist; }; auto ff = [&](int start) { using T = tuple; vector>dist(N, vector(2, INF)); dist[start][0] = 0; priority_queue, greater>que; que.push({dist[start][0], start, 0}); while(que.size()) { auto[cost, now, bit] = que.top(); que.pop(); if(dist[now][bit] != cost) continue; for(auto e: g[now]) { if(CHMIN(dist[e][bit^1], cost + 1)) { que.push({dist[e][bit^1], e, bit^1}); } } } return dist; }; auto distS = ff(S); auto distG = ff(G); int cost = distS[G][P & 1]; vectorans; REP(i, N) { if(min(distS[i][0] + distG[i][0^(P&1)], distS[i][1] + distG[i][1^(P&1)]) <= P) { ans.emplace_back(i); } } out(ans.size()); for(auto &e:ans)cout << e + 1 << endl; }