#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define sqr(x) ((x)*(x)) #define cbr(x) ((x)*(x)*(x)) #define rep(c, i, n) for((i)=(c); (i)<(n); (i)++) /** //Geometry struct pt { long long x, y; }; double vecmul(pt a, pt b) { return (a.x*b.y - b.x*a.y); } double dist(double ax, double ay, double bx, double by) { return sqrt(sqr(ax - bx) + sqr(ay - by)); } */ //DBG templatevoid printarr(T a[], T2 sz, T2 beg = 0) { for (T2 i = beg; i vertex[N]; queue bfsQ; vector path[N]; int vis[N]; int dist[N]; int main() { cin >> n >> m >> s >> f; s--; f--; int i,x,y,j; rep(0,i,m) { cin >> x >> y; x--; y--; vertex[x].push_back(y); vertex[y].push_back(x); } //visited 0, distance to everything is inf. memset(dist, -1, sizeof dist); memset(vis, 0, sizeof vis); dist[s] = 0; vis[s] = 1; path[s].push_back(s); bfsQ.push(s); int minDist=-1; while (!bfsQ.empty()) { int u = bfsQ.front(); bfsQ.pop(); for (int i : vertex[u]) { if (!vis[i]) { vis[i] = 1; dist[i] = dist[u]+1; path[i] = path[u]; path[i].push_back(i); bfsQ.push(i); } } } cout << dist[f] << endl; rep(0, i, path[f].size()) { path[f][i]++; } copy(path[f].begin(), path[f].end(), ostream_iterator(cout, " ")); return 0; }