The number of shortest paths can be exponential. With a source, 3 other nodes, and 4 edges, you can make 2 shortest paths, by adding 3 more nodes and 4 more edges, you can get 4 paths. So at least you can have $$$2^{M/4}$$$ shortest paths.

Auto comment: topic has been updated by Abdelrahman_Elhawary (previous revision, new revision, compare).

I slightly modified the bfs code.

counter[i] will be no more than the number of edges entering the vertex. This information is enough for us to understand whether the navigator will be rebuilt

My submission during the contest :72160563

while(!q.empty()) {
        auto v = q.front();
        q.pop();
        for (auto u : gt[v]) {
            if (d[u] == d[v] + 1) {
                counter[u]++;
            }
            if (d[u] == 1e9) {
                d[u] = d[v] + 1;
                q.push(u);
            }
        }
    }