#include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; const int INF = 1e8; vector G[100000]; int dist_t[100000][2]; int dist_s[100000][2]; int N, M, K; int s, t; void dijkstra(int s, int d[][2]){ priority_queue, greater

> que; for(int i = 0; i < N; i++){ d[i][0] = INF; d[i][1] = INF; } d[s][0] = 0; que.push(P(0, s)); while(!que.empty()){ P p = que.top();que.pop(); int v = p.second; int dist = p.first; if(d[v][dist%2] < dist) continue; for(int i = 0; i < G[v].size(); i++){ int to = G[v][i]; if(d[v][dist%2] + 1 < d[to][(dist+1)%2]){ d[to][(dist+1)%2] = d[v][dist%2] + 1; que.push(P(d[to][(dist+1)%2], to)); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N >> M >> K; cin >> s >> t; s--; t--; for(int i = 0; i < M; i++){ int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } dijkstra(s, dist_s); dijkstra(t, dist_t); vector ans; for(int i = 0; i < N; i++){ if(K%2 == 1){ if(dist_s[i][1]+dist_t[i][0] <= K) { ans.push_back(i); continue; } if(dist_s[i][0]+dist_t[i][1] <= K) { ans.push_back(i); continue; } }else{ if(dist_s[i][0]+dist_t[i][0] <= K) { ans.push_back(i); continue; } if(dist_s[i][1]+dist_t[i][1] <= K) { ans.push_back(i); continue; } } } if(ans.size() == 0){ cout << -1 << endl; return 0; } cout << ans.size() << endl; for(int i : ans) cout << i+1 << endl; }