#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define int long long #define double long double typedef vector VI; typedef pair pii; typedef vector VP; typedef vector VS; typedef priority_queue PQ; templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #define fore(i,a) for(auto &i:a) #define REP(i,n) for(int i=0;i, greater > q2; int N, M, P, s, g; vector G; VI d; int q[200005]; void bfs(int s) { REP(i, N)d[i] = INF; int qh = 0, qt = 0; q[qh++] = s; d[s] = 0; while (qt < qh) { int x = q[qt++]; for (int y : G[x]) { if (d[y] == INF) { d[y] = d[x] + 1; q[qh++] = y; } } } } signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> P >> s >> g; G.resize(N); d.resize(N); s--; g--; REP(i, M) { int v, u; cin >> u >> v; u--; v--; G[v].push_back(u); G[u].push_back(v); } VI ans; bfs(s); VI dis1 = d; bfs(g); VI dis2 = d; REP(i, N) { if (P - dis1[i] - dis2[i] < 0)continue; if ((P - dis1[i] - dis2[i]) % 2 == 0)ans.push_back(i); else { if (P - dis1[i] - dis2[i] - 1 < 0)continue; fore(to, G[i]) { if (P - dis1[i] - 1 - dis2[to] < 0)continue; if ((P - dis1[i] - 1 - dis2[to]) % 2 == 0) { ans.push_back(i); break; } if ((P - dis2[i] - 1 - dis1[to]) % 2 == 0) { ans.push_back(i); break; } } } } if (ans.size() == 0) { cout << -1 << endl; return 0; } SORT(ans); cout << ans.size() << endl; fore(i, ans)cout << i + 1 << '\n'; return 0; }