Day 177-Q2 — 2026-10-13 | 速い泥棒の警官と泥棒（泥棒が 1 手で距離 2 まで動けると、解体可能グラフでも逃げ切られる）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n)]
    for i in range(m):
        u = int(data[2 + 2 * i]) - 1
        v = int(data[3 + 2 * i]) - 1
        adj[u].append(v)
        adj[v].append(u)
    nb = [sum(1 << w for w in adj[v]) for v in range(n)]          # 開近傍
    cl = [nb[v] | (1 << v) for v in range(n)]                     # 閉近傍 N[v]
    full = (1 << n) - 1

    # R2[c][r]: 警官が c にいるとき、泥棒が r から 1 手で行ける頂点（長さ 2 以下、c を通らない、c で止まらない）
    R2 = [[0] * n for _ in range(n)]
    for r in range(n):
        ns = adj[r]
        d = len(ns)
        pre = [0] * (d + 1)
        for i in range(d):
            pre[i + 1] = pre[i] | nb[ns[i]]
        suf = [0] * (d + 1)
        for i in range(d - 1, -1, -1):
            suf[i] = suf[i + 1] | nb[ns[i]]
        ball2 = cl[r] | pre[d]                                     # 距離 2 以内
        for c in range(n):
            if c != r:
                R2[c][r] = ball2 & ~(1 << c)
        for i, c in enumerate(ns):                                 # c が r の隣: c を経由する行き先を除く
            R2[c][r] = (cl[r] | pre[i] | suf[i + 1]) & ~(1 << c)

    INF = -1
    cop = [[INF] * n for _ in range(n)]      # 警官の手番での残り手数
    rob = [[INF] * n for _ in range(n)]      # 泥棒の手番での残り手数
    dcop = [0] * n                           # dcop[c]: 警官手番で値が確定した r の集合
    drob = [0] * n
    for c in range(n):
        cop[c][c] = rob[c][c] = 0
        dcop[c] = drob[c] = 1 << c
    newrob = [1 << c for c in range(n)]      # 直前の段で確定した泥棒手番
    v = 0
    while True:
        # 警官手番 (c', r): 隣 c ∈ N[c'] の泥棒手番 (c, r) が段 v で確定 → 値 v+1
        newcop = [0] * n
        anyc = False
        for c2 in range(n):
            acc = 0
            for c in adj[c2]:
                acc |= newrob[c]
            acc |= newrob[c2]
            acc &= ~dcop[c2]
            if acc:
                anyc = True
                newcop[c2] = acc
                dcop[c2] |= acc
                row = cop[c2]
                while acc:
                    low = acc & -acc
                    row[low.bit_length() - 1] = v + 1
                    acc ^= low
        if not anyc:
            break
        v += 1
        # 泥棒手番 (c, r): 行き先 R2[c][r] がすべて確定（値 ≤ v）→ 値 v（最大を取る）
        newrob = [0] * n
        for c in range(n):
            if not newcop[c]:
                continue
            dc = dcop[c]
            und = full & ~drob[c]
            row = R2[c]
            got = 0
            while und:
                low = und & -und
                r = low.bit_length() - 1
                und ^= low
                if row[r] & ~dc == 0:
                    got |= low
                    rob[c][r] = v
            if got:
                newrob[c] = got
                drob[c] |= got
    best, arg = -1, -1
    for c in range(n):
        if dcop[c] == full:
            t = max(cop[c])
            if best < 0 or t < best:
                best, arg = t, c
    print(-1 if best < 0 else f"{best} {arg + 1}")


main()