图上的 DFS 与 BFS、连通性

// 标准答案 —— 两个问题都故意用「完全不是搜索」的思路做一遍
//
// 输入：第一行 n m s（n 个点、m 条无向边、起点 s），接下来 m 行每行两个端点
//       ⚠ 可能有自环、可能有重边、**整张图不保证连通**
// 输出：第一行 连通块个数；第二行 从 s 到每个点的最短边数（走不到写 -1）
//
// 为什么标准答案要换思路（第 9 章、第 15 章那条规矩）：
//   如果这里也写一遍 DFS / BFS，那和 fast.cpp 就是同一个想法写了两遍 ——
//   只能验出打字错误，验不出想法错误。所以两问都换：
//
//   ① 连通块：**朴素并查集**。它根本不「走」图，只是把每条边的两个端点合并到一起，
//      最后数一数还剩几个根。（并查集第 36 章才正式讲，这里用的是最朴素的版本：
//      不路径压缩、不按秩合并，find 一路往上爬。n 很小，够用。）
//
//   ② 最短路：**枚举所有简单路径**。从 s 出发一条路走到黑，
//      每走到一个点就用「当前这条路的长度」去更新它的答案，然后回溯换一条路走。
//      它不需要任何关于「最短」的洞察 —— 把所有路都走一遍，最短的自然就在里面。
//      代价是指数级：n 稍微大一点就跑不完了（正文第 4 步有实测）。
//
// 这两个思路和 fast.cpp 的 DFS 染色 / BFS 没有任何共同之处，
// 所以它们同时错到一块去的概率极低 —— 这正是对拍要的。

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

int n, m, s;
vector<vector<int>> g;          // 只有第 ② 问的枚举要用它
vector<int> best;               // best[v] = 目前找到的、从 s 到 v 的最短长度
vector<char> onPath;

/* ---------- ① 朴素并查集：不搜索，只合并 ---------- */
vector<int> fa;
int find(int x) { return fa[x] == x ? x : find(fa[x]); }   // 不压缩路径，最朴素的版本

/* ---------- ② 枚举所有简单路径 ---------- */
void walk(int u, int len) {
    if (len < best[u]) best[u] = len;
    for (int v : g[u]) {
        if (onPath[v]) continue;        // 同一条路上不能重复经过一个点，否则会绕圈绕不完
        onPath[v] = 1;
        walk(v, len + 1);
        onPath[v] = 0;                  // ★ 回溯：撤销，换一条路走（第 4 章那一套）
    }
}

int main() {
    if (!(cin >> n >> m >> s)) return 0;
    g.assign(n + 1, {});
    fa.resize(n + 1);
    for (int i = 1; i <= n; i++) fa[i] = i;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);              // 无向图存两遍（第 29 章那条）
        int a = find(u), b = find(v);
        if (a != b) fa[a] = b;          // 一条边 = 两个端点在同一块里
    }

    // ① 还剩几个根，就有几个连通块。孤立点（一条边都没有）自己就是一个根，
    //    所以它天然被算成了一块 —— 这一点后面会变成一个专门的错误版本。
    int blocks = 0;
    for (int i = 1; i <= n; i++) if (find(i) == i) blocks++;

    // ②
    best.assign(n + 1, INT_MAX);
    onPath.assign(n + 1, 0);
    onPath[s] = 1;
    walk(s, 0);

    cout << blocks << "\n";
    for (int i = 1; i <= n; i++)
        cout << (best[i] == INT_MAX ? -1 : best[i]) << " \n"[i == n];
    return 0;
}

// 图上的 DFS 与 BFS —— ★ 这份代码几乎是从第 13、14 章原样抄过来的
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得多。
//
// ★ 这一章唯一的关键一步：**网格是图的一个特例**。
//
//   第 13 章数连通块，第 14 章走最短路，用的是同一个套路：
//   「站在一个位置上 → 看它的邻居 → 没去过就去」。
//   那时候「邻居」的意思是「上下左右四格」，所以代码里写的是：
//
//       for (int d = 0; d < 4; d++) {
//           int x = i + dx[d], y = j + dy[d];
//           if (x < 0 || x >= n || y < 0 || y >= m) continue;   // 出界
//           if (g[x][y] != '1') continue;                       // 是墙
//           if (vis[x][y]) continue;                            // 去过了
//           ...
//       }
//
//   现在换成一般的图，「邻居」由邻接表直接给出，那一段就塌成一行：
//
//       for (int v : g[u]) {
//           if (vis[v]) continue;                               // 去过了
//           ...
//       }
//
//   **少了「出界」和「是墙」两个判断**，因为邻接表里存的本来就全是合法的邻居 ——
//   网格里那两句 if，本质上就是在临时地、每次重新地回答「谁是我的邻居」。
//   除此之外：DFS 还是那个 DFS，BFS 还是那个 BFS，vis 还是入队时打，
//   「第一次到达 = 最短到达」还是成立。**一个字都不用改。**
//
// 复杂度：两问都是 O(n + m) —— 每个点进出一次，每条边被两端各看一次
//         （第 29 章那张表里「表扫一遍 = 2m」的那一行）。
//
// ⚠ 自环和重边对搜索完全无害：自环指向自己，vis 早就是 1 了；
//   重边只是让同一个邻居出现两次，第二次照样被 vis 挡住。**不用特意去重。**

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

int n, m, s;
vector<vector<int>> g;
vector<char> vis;

/* ---------- ① DFS 染色数连通块 —— 第 13 章 fast.cpp 的图版 ---------- */
void dfs(int u) {
    vis[u] = 1;                          // 先给脚下这个点染色
    for (int v : g[u]) {                 // ★ 唯一变了的一行：邻居从「四个方向」变成邻接表
        if (vis[v]) continue;            //   已经染过了
        dfs(v);                          //   走过去，重复同样的事
    }
}

int main() {
    if (!(cin >> n >> m >> s)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);               // 无向图存两遍（第 29 章）
    }

    // ① 每发起一次 dfs，就意味着发现了一块新的 —— 和第 13 章那两层循环一模一样，
    //    只是「扫每个格子」变成了「扫每个点」。
    //    ⚠ 必须扫过 1..n 的每一个点：一条边都没有的孤立点，它自己就是一个连通块。
    vis.assign(n + 1, 0);
    int blocks = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            blocks++;
            dfs(i);
        }
    }

    // ② BFS 求最短边数 —— 第 14 章 fast.cpp 的图版
    //    队列先进先出，先进队列的一定离 s 更近，所以队列天然按距离排好了序。
    //    ★ 第一次到达 = 最短到达。
    vector<int> dist(n + 1, -1);         // -1 = 还没到过（也正好是「走不到」要输出的值）
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {             // ★ 又是同一行
            if (dist[v] != -1) continue; // 来过了，而且那次一定不比这次远
            dist[v] = dist[u] + 1;       // ← 入队时就定下距离并标记，不是出队时
            q.push(v);                   //   （出队才标记 = BFS 的头号错误，正文第 9 步）
        }
    }

    cout << blocks << "\n";
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}

// ★ 把第 13 章那张 8×8 地图，真的转成一张图
//
// 这份代码存在的理由只有一个：**把「网格是图的一个特例」从一句话变成一件可验证的事。**
//
// 转换规则就是那句话本身：
//   · 每个**陆地格**是一个点（水格不建点）；
//   · 两个相邻（上下左右）的陆地格之间连一条无向边。
//
// 编号按行优先，从 1 开始 —— 于是 (0,0) 是 1 号点，(n-1,m-1) 是最后一个点。
//
// 输出的格式正好是本章那道题的输入（`点数 边数 起点` + 边表），所以可以直接接管道：
//
//     ./gridToGraph < map.txt | ./fast
//
// 跑出来第一行必须是 **3** —— 和第 13 章 fast.cpp 在同一张地图上数出的连通块数一模一样；
// 第二行里终点那个位置必须是 **16** —— 和第 14 章 fast.cpp 走出的最短路一模一样。
//
//   ★ 两份代码：一份满脑子「上下左右四个方向」，一份只知道 `for (int v : g[u])`，
//     谁都没听说过对方，**答案却一个字不差**。这就是「网格是图的一个特例」的证据。
//
// scripts/check-viz.mjs 会把这条管道真的跑一遍，和第 13、14 章的 C++ 逐个对答案。
//
// 用法：./gridToGraph          读网格，输出图（可以直接管道给 fast / brute）
//       ./gridToGraph info     读网格，输出「谁变成了几号点」的说明
//
// 输入格式和第 13、14 章完全一致：第一行 n m，接下来 n 行每行 m 个字符，'1' 是陆地。

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

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int main(int argc, char** argv) {
    bool info = (argc > 1 && string(argv[1]) == "info");

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    // ① 给每个陆地格发一个编号（水格是 0，表示「这里没有点」）
    vector<vector<int>> id(n, vector<int>(m, 0));
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1') id[i][j] = ++cnt;

    // ② 相邻的两个陆地格之间连一条边。
    //    只往「下」和「右」看，每条边就正好被造一次（往上/往左看会把每条边造两遍）。
    vector<pair<int, int>> es;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] != '1') continue;
            for (int d = 1; d <= 3; d += 2) {            // 只取 dx/dy 里的「下」和「右」
                int x = i + dx[d], y = j + dy[d];
                if (x >= n || y >= m) continue;
                if (g[x][y] != '1') continue;
                es.push_back({id[i][j], id[x][y]});
            }
        }

    // ③ 起点取 (0,0)（它在第 13、14 章里也是起点）。万一它是水，就退而取第一个陆地格。
    int s = (n > 0 && m > 0 && g[0][0] == '1') ? id[0][0] : 1;
    int target = (g[n - 1][m - 1] == '1') ? id[n - 1][m - 1] : -1;

    if (!info) {
        cout << cnt << " " << es.size() << " " << s << "\n";
        for (auto [u, v] : es) cout << u << " " << v << "\n";
        return 0;
    }

    printf("%d x %d 的网格里有 %d 个陆地格 -> %d 个点，%d 条边\n", n, m, cnt, cnt, (int)es.size());
    printf("起点 (0,0) 是 %d 号点，终点 (%d,%d) 是 %d 号点\n", s, n - 1, m - 1, target);
    printf("每个格子对应的编号（0 = 水，这里没有点）：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) printf("%4d", id[i][j]);
        printf("\n");
    }
    printf("\n把它交给本章的 fast.cpp（./gridToGraph < map | ./fast）：\n");
    printf("  第一行 = 连通块个数，必须和第 13 章 fast.cpp 的答案一样；\n");
    printf("  第二行第 %d 个数 = 到终点的最短边数，必须和第 14 章 fast.cpp 的答案一样。\n", target);
    return 0;
}

// ✗ 错误版本一：BFS 在**出队**的时候才标记，不是入队时标记
//
// 这是 BFS 的头号错误，第 14 章就点过名，但那时候只说了「会退化成暴力」。
// 在图上它更狠一点 —— **答案本身就是错的**，不只是慢。
//
// 为什么错：一个点可能被好几个邻居同时看见，于是被塞进队列好几次。
//   每塞一次都会重新写一遍它的 dist，而后写的那次不一定更近 ——
//   于是一个明明距离 1 的点，可能被后来的某次入队改成 2。
//
//   ★ 「入队时标记」保证的是：**一个点只会被记一次距离，而且是第一次（也就是最短的那次）**。
//   出队才标记，这个保证就没了。
//
// 只改了 BFS 那一段，其它一个字没动。

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

int n, m, s;
vector<vector<int>> g;
vector<char> vis;

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (vis[v]) continue;
        dfs(v);
    }
}

int main() {
    if (!(cin >> n >> m >> s)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vis.assign(n + 1, 0);
    int blocks = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) { blocks++; dfs(i); }

    vector<int> dist(n + 1, -1);
    vector<char> done(n + 1, 0);         // ✗ 「已处理」标记，出队时才打
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (done[u]) continue;
        done[u] = 1;                     // ✗ 出队才标记 —— 晚了
        for (int v : g[u]) {
            if (done[v]) continue;
            dist[v] = dist[u] + 1;       // ✗ 已经在队列里的点，距离被后来者覆盖掉
            q.push(v);
        }
    }

    cout << blocks << "\n";
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}

// ✗ 错误版本二：用 DFS 求最短路（拿递归深度当距离）
//
// 想法听起来很顺：反正 DFS 也能把整块都走一遍，顺手记一下「我是第几层走到你的」不就完了？
//
// 错在哪：DFS 是**一条路走到黑**，它到达一个点时走的那条路，
//   通常不是最短的那条 —— 而 vis 一打上，它就再也不会用更短的路来看你一眼了。
//
//   ★ 一句话：**DFS 的深度是「我沿着这条路走了多久」，BFS 的距离是「最少要走多久」。**
//   两者只有在树上才必然相等（树上任意两点之间只有一条路）。
//
// 更阴的地方：它的答案**不是随机地错**，而是「谁先被走到，谁的距离就定死了」——
//   换一个邻接表的存边顺序，错法就变一个样。第 9 步的动画里能看到这一点。
//
// 只改了第 ② 问，连通块那一问是对的。

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

int n, m, s;
vector<vector<int>> g;
vector<char> vis;
vector<int> dist_;

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (vis[v]) continue;
        dfs(v);
    }
}

// ✗ 拿递归深度当最短距离
void dfsDist(int u, int d) {
    dist_[u] = d;
    for (int v : g[u]) {
        if (dist_[v] != -1) continue;
        dfsDist(v, d + 1);
    }
}

int main() {
    if (!(cin >> n >> m >> s)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vis.assign(n + 1, 0);
    int blocks = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) { blocks++; dfs(i); }

    dist_.assign(n + 1, -1);
    dfsDist(s, 0);

    cout << blocks << "\n";
    for (int i = 1; i <= n; i++)
        cout << dist_[i] << " \n"[i == n];
    return 0;
}

// ✗ 错误版本三：数连通块时只从「有边的点」发起 DFS —— 孤立点漏掉了
//
// 写法本身看着很讲道理：「一个点连边都没有，还搜它干嘛？」
// 可是**一个孤立点自己就是一个连通块**（它和自己连通，仅此而已）。
//
// ★ 这个 bug 的可怕之处不在代码，在数据：
//   只要生成器保证图是连通的（造一棵生成树再加边 —— 这是绝大多数人写图生成器时的条件反射），
//   图里就永远不会有孤立点，这份代码永远是对的。
//   本章第 12 步实测：那种「顺手保证连通」的数据下，它 **0 / 300**。
//
// 只改了那一处判断。

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

int n, m, s;
vector<vector<int>> g;
vector<char> vis;

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (vis[v]) continue;
        dfs(v);
    }
}

int main() {
    if (!(cin >> n >> m >> s)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vis.assign(n + 1, 0);
    int blocks = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].empty()) continue;      // ✗ 「没有边的点不用管」—— 它自己就是一块
        if (!vis[i]) { blocks++; dfs(i); }
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    cout << blocks << "\n";
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}

// 和 fast.cpp 完全一样的答案，但**一行递归都没有**
//
// 这份代码为什么存在：因为 fast.cpp 在大图上会**段错误**。
//
//   本机实测（./genBig 500000，m = 2n）：递归版直接 signal 11 挂掉，
//   而这一份 0.7 秒跑完。`ulimit -s unlimited` 之后递归版能跑，但那是在改机器，不是在改代码 ——
//   评测机上你改不了。
//
// ★ 原因：**图上 DFS 的递归深度上限是「点数」，不是「层数」。**
//   网格题里其实也一样（第 13 章那张图要是 1000×1000，同样会炸），
//   只是那时候数据小，没碰上。这和第 21 章 stairsDeep.cpp 那个
//   「记忆化递归 30 万层直接段错误、递推 1000 万都没事」是**同一个坑**。
//
// 两种改法，这里各用一次：
//   ① 数连通块 —— 干脆改用 **BFS 染色**。
//      「哪些点连在一起」这件事跟走的顺序毫无关系，DFS 能做的 BFS 一样能做，
//      而 BFS 的队列在堆上，没有深度问题。**能用 BFS 就别用递归 DFS。**
//   ② 真需要 DFS 的顺序时 —— 用**手写栈**把递归摊开：
//      栈里存 (当前点, 下一条要看的边是第几条)，正好就是递归帧里的那两个局部变量。
//      本文件的 maxDepth 就是这么数出来的，它等于递归版要压多少层栈帧。
//
// 用法：./fastIter            和 fast.cpp 一样的输出（check:viz 300 组逐组比对）
//       ./fastIter depth      再多打一行：手写栈最深压到多少层
//
// ⚠ 别把这理解成「递归不能用」。n 只有几万时递归版更短更好读，用它；
//   n 上十万，先想一想这个深度。**知道界在哪，比背「递归不安全」有用。**

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

int main(int argc, char** argv) {
    bool showDepth = (argc > 1 && string(argv[1]) == "depth");

    int n, m, s;
    if (scanf("%d %d %d", &n, &m, &s) != 3) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        if (scanf("%d %d", &u, &v) != 2) return 0;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // ① 连通块：BFS 染色。和 fast.cpp 的 DFS 版给出同一个答案 ——
    //    连通块只关心「谁和谁连着」，跟访问顺序无关。
    vector<char> vis(n + 1, 0);
    int blocks = 0;
    {
        vector<int> q;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            blocks++;
            q.clear();
            q.push_back(i);
            vis[i] = 1;
            for (size_t h = 0; h < q.size(); h++)
                for (int v : g[q[h]])
                    if (!vis[v]) { vis[v] = 1; q.push_back(v); }
        }
    }

    // ② 最短路：本来就是 BFS，一个字都不用改
    vector<int> dist(n + 1, -1);
    {
        vector<int> q;
        dist[s] = 0;
        q.push_back(s);
        for (size_t h = 0; h < q.size(); h++)
            for (int v : g[q[h]])
                if (dist[v] == -1) { dist[v] = dist[q[h]] + 1; q.push_back(v); }
    }

    printf("%d\n", blocks);
    for (int i = 1; i <= n; i++) printf("%d%c", dist[i], " \n"[i == n]);

    if (showDepth) {
        // ③ 手写栈版的 DFS：栈里那两个字段，就是递归帧里的两个局部变量。
        //    它压到多少层，递归版就要压多少层栈帧 —— 这个数就是段错误的根源。
        vector<char> seen(n + 1, 0);
        vector<pair<int, size_t>> st;                // (点, 下一条要看的边是第几条)
        size_t maxDepth = 0;
        for (int i = 1; i <= n; i++) {
            if (seen[i]) continue;
            st.clear();
            seen[i] = 1;
            st.push_back({i, 0});
            while (!st.empty()) {
                maxDepth = max(maxDepth, st.size());
                int u = st.back().first;
                size_t k = st.back().second;
                if (k == g[u].size()) { st.pop_back(); continue; }
                st.back().second = k + 1;            // 这一条边看过了，下次从下一条开始
                int v = g[u][k];
                if (seen[v]) continue;
                seen[v] = 1;
                st.push_back({v, 0});                // ← 相当于递归调用 dfs(v)
            }
        }
        printf("手写栈最深压到 %zu 层（递归版就要压这么多层栈帧，%d 个点里的 %.1f%%）\n",
               maxDepth, n, 100.0 * (double)maxDepth / n);
    }
    return 0;
}

// 图上的 DFS 与 BFS —— ★ 这份代码几乎是从第 13、14 章原样抄过来的
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得多。
//
// ★ 这一章唯一的关键一步：**网格是图的一个特例**。
//
//   第 13 章数连通块，第 14 章走最短路，用的是同一个套路：
//   「站在一个位置上 → 看它的邻居 → 没去过就去」。
//   那时候「邻居」的意思是「上下左右四格」，所以代码里写的是：
//
//       for (int d = 0; d < 4; d++) {
//           int x = i + dx[d], y = j + dy[d];
//           if (x < 0 || x >= n || y < 0 || y >= m) continue;   // 出界
//           if (g[x][y] != '1') continue;                       // 是墙
//           if (vis[x][y]) continue;                            // 去过了
//           ...
//       }
//
//   现在换成一般的图，「邻居」由邻接表直接给出，那一段就塌成一行：
//
//       for (int v : g[u]) {
//           if (vis[v]) continue;                               // 去过了
//           ...
//       }
//
//   **少了「出界」和「是墙」两个判断**，因为邻接表里存的本来就全是合法的邻居 ——
//   网格里那两句 if，本质上就是在临时地、每次重新地回答「谁是我的邻居」。
//   除此之外：DFS 还是那个 DFS，BFS 还是那个 BFS，vis 还是入队时打，
//   「第一次到达 = 最短到达」还是成立。**一个字都不用改。**
//
// 复杂度：两问都是 O(n + m) —— 每个点进出一次，每条边被两端各看一次
//         （第 29 章那张表里「表扫一遍 = 2m」的那一行）。
//
// ⚠ 自环和重边对搜索完全无害：自环指向自己，vis 早就是 1 了；
//   重边只是让同一个邻居出现两次，第二次照样被 vis 挡住。**不用特意去重。**

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

int n, m, s;
vector<vector<int>> g;
vector<char> vis;

/* ---------- ① DFS 染色数连通块 —— 第 13 章 fast.cpp 的图版 ---------- */
void dfs(int u) {
    vis[u] = 1;                          // 先给脚下这个点染色
    for (int v : g[u]) {                 // ★ 唯一变了的一行：邻居从「四个方向」变成邻接表
        if (vis[v]) continue;            //   已经染过了
        dfs(v);                          //   走过去，重复同样的事
    }
}

int main() {
    if (!(cin >> n >> m >> s)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);               // 无向图存两遍（第 29 章）
    }

    // ① 每发起一次 dfs，就意味着发现了一块新的 —— 和第 13 章那两层循环一模一样，
    //    只是「扫每个格子」变成了「扫每个点」。
    //    ⚠ 必须扫过 1..n 的每一个点：一条边都没有的孤立点，它自己就是一个连通块。
    vis.assign(n + 1, 0);
    int blocks = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            blocks++;
            dfs(i);
        }
    }

    // ② BFS 求最短边数 —— 第 14 章 fast.cpp 的图版
    //    队列先进先出，先进队列的一定离 s 更近，所以队列天然按距离排好了序。
    //    ★ 第一次到达 = 最短到达。
    vector<int> dist(n + 1, -1);         // -1 = 还没到过（也正好是「走不到」要输出的值）
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {             // ★ 又是同一行
            if (dist[v] != -1) continue; // 来过了，而且那次一定不比这次远
            dist[v] = dist[u] + 1;       // ← 入队时就定下距离并标记，不是出队时
            q.push(v);                   //   （出队才标记 = BFS 的头号错误，正文第 9 步）
        }
    }

    cout << blocks << "\n";
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
    return 0;
}