PS: Brute-force algorithm means: starting DFS from node 1, maintaining a vis array to indicate whether a node has been visited:

void dfs(int u, int sum = 0) {
    if (u == n) {
        ans[sum]++;
        return; 
    }
    vis[u] = 1;
    for (auto [v, w] : d[u]) if (!vis[v]) {
        dfs(v, sum + w);
    }
    vis[u] = 0;
}

Origin Solution: Build a DFS tree, and construct a virtual tree using the endpoints of back edges as key nodes. Then directly run the brute-force algorithm.

This works because the complexity of the brute-force algorithm is \(O(2^kn)\), where \(k\) is the number of back edges in the DFS tree.

Because \(m \le n + 20\), we have \(k \le 21\).

After contraction, the complexity becomes \(O(2^k k)\), which is sufficient to pass.