CSES - Graph Girth

Let's consider a simpler problem: given a graph, find the shortest cycle that passes through node 1.

What does a cycle through node 1 look like? In any cycle through node 1, there exists two nodes $u$ and $v$ on that cycle such that there is a path from 1 to $u$ and 1 to $v$, and there is an edge between $u$ and $v$. The length of this cycle is $dist(1, u) + dist(1, v) + 1$.

One might now try to use BFS to find $dist(1, i)$ for each $i$ in $O(N + M)$ time and then check for each edge $(u, v)$ whether $dist(1, u) + dist(1, v) + 1$ is minimal.

Of course, this means that we might count a "cycle" like $1 \rightarrow x \rightarrow u \rightarrow v \rightarrow x \rightarrow 1$. However, this doesn't matter for our original problem, since the shortest cycle will always be shorter than such a "cycle".

There's one problem with this approach though: if the edge $(u, v)$ is on the path from node 1 to node $v$, then $1 \rightarrow u \rightarrow v \rightarrow 1$ isn't a cycle! And this time, it does matter in our original problem!

Fortunately, there's a relatively simple fix.

Instead of first finding all $dist(1, i)$ and then checking for the minimum, do both at the same time during the BFS.

Now to prevent "backtracking", we only consider $dist(1, u) + dist(1, v) + 1$ as a minimum if we're currently at node $u$ and $dist(1, u) \leq dist(1, v)$.

This algorithm runs in $O(N + M)$ time. Since $N$ and $M$ are so small, we can just apply this algorithm for all nodes instead of just node 1.

The final complexity of this solution is thus $O(N(N + M))$.

int n,m,dist[2501],ans=MOD;
vi adj[2501];

int main() {
    setIO(); re(n,m);
    F0R(i,m) {
        int a,b; re(a,b);
        adj[a].pb(b), adj[b].pb(a);
    }
    FOR(i,1,n+1) {

int n,m,dist[2501],ans=MOD;
vi adj[2501];

int main() {
    setIO(); re(n,m);
    F0R(i,m) {
        int a,b; re(a,b);
        adj[a].pb(b), adj[b].pb(a);
    }
    FOR(i,1,n+1) {