Code : The Shortest Path

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

class Graph {
  public:
    int n;
    vector<vector<int>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }
    void bfs(int src, int target) {
        vector<int> level(n, -1), parent(n, -1);
        queue<int> q;
        level[src] = 0;
        q.push(src);

        while (!q.empty()) {
            int now = q.front();
            q.pop();

            for (auto child : adj[now]) {
                if (level[child] == -1) {
                    level[child] = level[now] + 1;
                    parent[child] = now;
                    q.push(child);
                }
            }
        }

        cout << level[target] << endl;
        if (level[target] == -1) {
            return;
        }
        vector<int> res;
        int now = target;
        while (now != -1) {
            res.push_back(now);
            now = parent[now];
        }
        reverse(res.begin(), res.end());
        for (auto &ele : res) {
            cout << ele + 1 << " ";
        }
        cout << endl;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    int src, target;
    cin >> src >> target;
    src--;
    target--;

    auto &adj = g.adj;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    g.bfs(src, target);
}

int main() {
    solve();
    return 0;
}