Day 176-Q1 — 2026-10-12 | 1 人の警官と泥棒（閉路のある対局グラフを後退解析し、最短の捕獲時間を求める）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[v] for v in range(n)]                 # 閉近傍 N[v]（その場に留まる手を含む）
    for k in range(m):
        u = int(data[2 + 2 * k]) - 1
        v = int(data[3 + 2 * k]) - 1
        adj[u].append(v)
        adj[v].append(u)
    INF = -1
    # 状態番号 c*n+r。C[s]: 警官の手番で残り何手で捕まえられるか、R[s]: 泥棒の手番
    C = [INF] * (n * n)
    R = [INF] * (n * n)
    cnt = [0] * (n * n)                          # 泥棒の手番で、まだ値の決まらない逃げ先の数
    for c in range(n):
        base = c * n
        for r in range(n):
            cnt[base + r] = len(adj[r])
    level = []                                   # 値 v の泥棒手番状態（R=v で確定）
    for c in range(n):
        s = c * n + c
        C[s] = 0
        R[s] = 0
        level.append(s)
    # 泥棒の逃げ先 r'==c（自分から捕まりに行く手）は C=0 で確定済みなので、カウンタを先に減らしておく
    for c in range(n):
        for r in adj[c]:
            if r != c:
                cnt[c * n + r] -= 1
    v = 0
    while level:
        # level: 値 v で確定した泥棒手番状態 → 警官手番の前の状態は値 v+1
        nxt_cop = []
        for s in level:
            c, r = divmod(s, n)
            for c2 in adj[c]:
                t = c2 * n + r
                if C[t] == INF:
                    C[t] = v + 1
                    nxt_cop.append(t)
        v += 1
        # 値 v で確定した警官手番状態 → 泥棒手番の前の状態のカウンタを減らす。0 になれば R=v
        level = []
        for s in nxt_cop:
            c, r = divmod(s, n)
            for r2 in adj[r]:
                t = c * n + r2
                if R[t] == INF and r2 != c:
                    cnt[t] -= 1
                    if cnt[t] == 0:
                        R[t] = v
                        level.append(t)
    best, best_c = None, -1
    for c in range(n):
        row = C[c * n:(c + 1) * n]
        if INF in row:
            continue
        w = max(row)
        if best is None or w < best:
            best, best_c = w, c
    if best is None:
        print(-1)
    else:
        print(best, best_c + 1)


main()