/*
 * @Author: e2hang 2099307493@qq.com
 * @Date: 2025-12-11 21:29:50
 * @LastEditors: e2hang 2099307493@qq.com
 * @LastEditTime: 2025-12-11 21:30:10
 * @FilePath: \undefinedd:\code\Git-DataStructureAlgorithms\模板\图\无权图BFS求最短路径.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

/*
 * 无权图（所有边权为 1）的最短路径算法
 * 采用 BFS（广度优先搜索）
 *
 * BFS 的性质：
 *   - 从起点 s 开始，按层扩展
 *   - 第一次到达某节点时，路径长度一定最短
 *
 * 支持功能：
 *   1. dist[v] 记录起点到 v 的最短距离
 *   2. prev[v] 记录 v 的前驱节点，用于重建最短路径（可选）
 */

int main() {
    int n, e;
    cin >> n >> e;

    vector<vector<int>> adj(n);  // 无权图邻接表
    int u, v;

    // 输入 e 条边（默认无向图，可改成有向图）
    for (int i = 0; i < e; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);  // 若为有向图，则删除这一行
    }

    int s;          // 起点
    cin >> s;

    //
    // BFS 初始化
    //
    const int INF = 1e9;
    vector<int> dist(n, INF);  // dist[i] = 到 i 的最短距离
    vector<int> prev(n, -1);   // prev[i] = i 的前驱（用于重建路径）
    queue<int> q;

    // 起点初始化
    dist[s] = 0;
    q.push(s);

    //
    // BFS 主循环
    //
    while (!q.empty()) {
        int x = q.front();
        q.pop();

        // 遍历所有邻居
        for (int y : adj[x]) {
            // 若 y 未被访问过（dist[y] == INF）
            if (dist[y] == INF) {
                dist[y] = dist[x] + 1;   // 更新最短距离
                prev[y] = x;             // 记录前驱（x -> y）
                q.push(y);               // 将 y 加入队列继续扩展
            }
        }
    }

    //
    // 输出所有点的最短距离
    //
    cout << "Shortest distances from " << s << ":" << endl;
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) cout << i << " : Unreachable" << endl;
        else cout << i << " : " << dist[i] << endl;
    }

    //
    // 可选：重建从 s 到某个 t 的最短路径
    //
    int t;
    cout << "Enter target node to reconstruct path: ";
    cin >> t;

    if (dist[t] == INF) {
        cout << "No path from " << s << " to " << t << endl;
    } else {
        vector<int> path;
        for (int cur = t; cur != -1; cur = prev[cur])
            path.push_back(cur);
        reverse(path.begin(), path.end());

        cout << "Path: ";
        for (int x : path) cout << x << " ";
        cout << endl;
    }

    return 0;
}