用C++解决以下问题：给定一张 N 个点，M 条边的 简单无向图（无重边无自环），以及一个起点 s 和终点 t。接下来进行 Q 次询问，每次询问请你回答： 给定 k，从 s 出发恰好经过 k 条边且不能 连续 走一条边两次到达 t 的路径数。

在 C++ 中解决这个问题，可以采用深度优先搜索（DFS）结合动态规划的方法。首先，我们需要构建一个邻接表来表示图，并维护两个数组，一个是记录每个顶点到终点 t 的最少步数，另一个是记录到达每个顶点所需的最小步数，同时遍历过的节点标记为已访问。

下面是大致步骤：

1. 定义一个函数 `dfs(int u, int parent, vector<int>& dist, vector<bool>& visited)`，其中 `u` 是当前节点，`parent` 是上一步的来源，`dist` 存储从起点到每个节点的步数，`visited` 用于记录是否已经访问过。
- 对于每个未访问的邻居 v，如果 `dist[u] + 1 < dist[v]`，说明我们找到了一条新路径，更新 `dist[v]` 并继续向下探索。
- 如果 `dist[u] + 1 == k` 且 v 直接连接到终点 t，则计数加一，因为这是一种符合条件的路径。

2. 初始化：设置起点 s 到所有其他节点的步数为 INT_MAX（无穷大），起点 s 的步数设为 0；并将起点 s 标记为已访问。

3. 使用动态规划遍历整个图，对每个节点执行 DFS，更新最少步数。

4. 接收 Q 次询问，对于每次询问，计算满足条件的路径数，即起点 s 到步数等于 k 且未连续走过同一条边两次直接到达 t 的路径数量。这可以通过查询 `dist[t]` 来获取。

#include <vector>
using namespace std;

// 假设邻接列表存放在 graph 数组中，每条边 (i, j) 表示 i 到 j 有边相连
int dfs(int u, int parent, vector<int>& dist, vector<bool>& visited, vector<vector<int>>& graph) {
    // ... 实现 dfs...
}

int countPaths(int n, int m, int s, int t, int k, vector<vector<int>>& graph) {
    vector<int> dist(n);
    vector<bool> visited(n, false);
    dist[s] = 0;
    visited[s] = true;

    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        for (int neighbor : graph[i]) {
            if (!visited[neighbor]) {
                dfs(neighbor, i, dist, visited, graph);
            }
        }
    }

    return dist[t] == k ? 1 : 0; // 如果 t 的步数是 k，返回路径数，否则为 0
}

int main() {
    int N, M, S, T, Q;
    cin >> N >> M >> S >> T >> Q;
    vector<vector<int>> graph(N); // 建立邻接列表

    // 输入边的信息
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // 无向图，添加双向边
    }

    for (int q = 0; q < Q; ++q) {
        int K;
        cin >> K;
        cout << countPaths(N, M, S, T, K, graph) << endl;
    }

    return 0;
}