#include #include #include #include #include #include using namespace std; const int MAXN = 1e5 + 5; bool isExit[MAXN]; int dist[2][MAXN]; vector graph[MAXN]; ifstream fin("escape.in"); ofstream fout("escape.out"); void BFS(int s, int mul, int *dist, int n) { queue q; for(int x = 1;x<=n;x++) dist[x] = -1; dist[s] = 0; q.push(s); while(q.empty()==false) { int x = q.front(); q.pop(); //cout << x << " -> " << dist[x] << '\n'; for(int y: graph[x]) { if(dist[y]==-1) { dist[y] = dist[x] + mul; q.push(y); } } } } int last[MAXN]; void BFSBuild(int s, int mul, int n) { queue q; for(int x = 1;x<=n;x++) dist[0][x] = -1; for(int x = 1;x<=n;x++) last[x] = -1; dist[0][s] = 0; q.push(s); while(q.empty()==false) { int x = q.front(); q.pop(); if(dist[0][x]>=dist[1][x]) continue; //cout << x << " ---> " << dist[0][x] << '\n'; for(int y: graph[x]) { //cout << " -> " << y << " " << dist[0][y] << " " << dist[1][y] << '\n'; if(dist[0][y]==-1) { dist[0][y] = dist[0][x] + mul; last[y] = x; q.push(y); } } } } void solveTestcase() { int n, m, a, b, s; fin >> n >> m >> a >> b >> s; for(int x = 1;x<=n;x++) isExit[x] = false; for(int x = 1;x<=n;x++) graph[x].clear(); for(int i = 0;i> u >> v; graph[u].push_back(v); graph[v].push_back(u); } int k; fin >> k; int eStart = -1; for(int i = 0;i> e; isExit[e] = true; if(i==0) eStart = e; } BFS(eStart, a, dist[1], n); BFSBuild(s, b, n); int x = -1; for(int e = 1;e<=n;e++) { //if(isExit[e]==true) // cout << dist[0][e] << " < " << dist[1][e] << '\n'; if(isExit[e]==true && dist[0][e]!=-1 && dist[0][e] v; while(x!=-1) { v.push_back(x); x = last[x]; } fout << v.size() << '\n'; reverse(v.begin(), v.end()); fout << v[0]; for(int i = 1;i> T; while(T--) solveTestcase(); }