//BFS
vector<int> BFS (int st_node) {
    vector<int> level(N, inf);  // nodes
    queue<pair<int, int>> q;
    q.push({st_node, 0});
    level[st_node] = 0;
    int cur_depth, cur_node;
    while (not q.empty()) {
        cur_node = q.front().first;
        cur_depth = q.front().second;
        q.pop();
        for (int neg : adj[cur_node]) {
            // neg : node
            if (level[neg] == inf) {
                // not visited before
                q.push({neg, cur_depth + 1});
                level[neg] = cur_depth + 1;
            }
        }
    }
    return level;
}

// BFS 2  half memory usage
vector<int> BFS2 (int st_node) {
    vector<int> dist(N, inf);
    queue<int> q;
    q.push(st_node);
    dist[st_node] = 0;
    int lvl = 0, cur_node = st_node, sz_q = SZ(q);
    for (; !q.empty(); lvl++, sz_q = SZ(q)) {
        while (sz_q--) {
            cur_node = q.front();
            q.pop();
            for (int neg : adj[cur_node]) {
                if (dist[neg] == inf) {
                    // not visited before
                    q.push(neg);
                    dist[neg] = lvl + 1;
                }
            }
        }
    }
    return dist;
}


// BFS path
vector<int> BFSPath (int st_node, int target) {
    vector<int> dist(N, inf);
    vector<int> parent(N, -1);
    queue<int> q;
    q.push(st_node);
    dist[st_node] = 0;
    int lvl = 0, cur_node = st_node, sz_q = SZ(q);
    bool found = false;
    for (; not found && SZ(q); lvl++, sz_q = SZ(q)) {
        while (not found && sz_q--) {
            cur_node = q.front();
            q.pop();
            for (int neg : adj[cur_node]) {
                if (dist[neg] == inf) {
                    // not visited before
                    dist[neg] = lvl + 1;
                    q.push(neg);
                    // path
                    parent[neg] = cur_node;
                    if (neg == target) {
                        found = true;
                        break;
                    }
                }
            }
        }
    }
    vector<int> path;
    while (target != -1) {
        path.push_back(target);
        // update
        target = parent[target];
    }
    reverse(path.begin(), path.end());
    return path;
}