Day 163-Q4 — 2026-09-28 — 無向グラフの最短閉路（内周 girth。全頂点から BFS し、木の親へ戻らない辺で閉じる長さの最小。深さで打ち切る）

📋 コピーimport sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    g = [[] for _ in range(n)]
    for i in range(m):
        u, v = int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1
        g[u].append(v)
        g[v].append(u)
    best = n + 1                          # 単純グラフの閉路は長さ n 以下
    for r in range(n):
        dist = [-1] * n
        par = [-1] * n
        dist[r] = 0
        q = deque([r])
        while q:
            u = q.popleft()
            du = dist[u]
            if 2 * du + 1 >= best:        # ここから見つかる候補は 2*du 以上。改善しないので打ち切る
                break
            for v in g[u]:
                if dist[v] == -1:
                    dist[v] = du + 1
                    par[v] = u
                    q.append(v)
                elif par[u] != v:         # 木の親へ戻る辺以外 = 閉路を閉じる辺
                    c = du + dist[v] + 1
                    if c < best:
                        best = c
    print(best if best <= n else -1)


main()