#include <bits/stdc++.h>
using namespace std;

vector<int> shortestPath(int n, vector<vector<int>>& adj, int src, int dest) {
    vector<int> dist(n, INT_MAX), parent(n, -1);
    queue<int> q;

    dist[src] = 0;
    q.push(src);

    // BFS
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }

    // Reconstruct path from src → dest
    vector<int> path;
    if (dist[dest] == INT_MAX) return path; // no path

    for (int v = dest; v != -1; v = parent[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    int n = 6;
    vector<vector<int>> adj = {
        {1,2}, {0,3}, {0,3}, {1,2,4}, {3,5}, {4}
    };

    int src = 0, dest = 5;
    vector<int> path = shortestPath(n, adj, src, dest);

    cout << "Shortest path from " << src << " to " << dest << ": ";
    for (int v : path) cout << v << " ";
}