秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 edges，数组中以 [a,b] 形式表示景点 a 与景点 b 之间有一条小路连通。小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 startA 和 startB。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一：移动至相邻景点留在原地如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。注意：小力和小扣一定会采取最优移动策略。示例 1：输入：edges = [[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]], startA = 3, startB = 5输出：3解释：第一回合，小力移动至 2 号点，小扣观察到小力的行动后移动至 6 号点；第二回合，小力移动至 5 号点，小扣无法移动，留在原地；第三回合，小力移动至 6 号点，小力追到小扣。返回 3。示例 2：输入：edges = [[1,2],[2,3],[3,4],[4,1]], startA = 1, startB = 3输出：-1解释：小力如果不动，则小扣也不动；否则小扣移动到小力的对角线位置。这样小力无法追到小扣。提示：edges 的长度等于图中节点个数3 <= edges.length <= 10^51 <= edges[i][0], edges[i][1] <= edges.length 且 edges[i][0] != edges[i][1]1 <= startA, startB <= edges.length 且 startA != startB

class Solution:    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:        n = len(edges)        graph = collections.defaultdict(list)        for fr, to in edges:            graph[fr].append(to)            graph[to].append(fr)        def bfs(fr, find_entry=False):            dist = collections.defaultdict(lambda: float("inf"))            q = collections.deque([fr])            steps = 0            nonlocal entry            while q:                for i in range(len(q)):                    cur = q.popleft()                    if cur in dist:                        continue                    if find_entry and cur in circle:                        entry = cur                        return                    dist[cur] = steps                    for neibor in graph[cur]:                        q.append(neibor)                steps += 1            return dist        parent = {}        depth = collections.defaultdict(int)  # 可以被用作 visited        circle = set()        entry = 0  # 环的入口        def cal_circle(node, p):            parent[node] = p            depth[node] = depth[p] + 1            for neibor in graph[node]:                if neibor == p:                    continue                if neibor not in depth:                    cal_circle(neibor, node)                elif depth[neibor] < depth[node]:                    # 检测到了环                    cur = node                    while cur != neibor:                        circle.add(cur)                        cur = parent[cur]                    circle.add(neibor)        cal_circle(1, 0)        d1, d2 = bfs(startA), bfs(startB)        bfs(startB, True)        if len(circle) > 3:            if d1[entry] > d2[entry] + 1:                return -1        if d1[startA] == 1:            return 1        ans = 1        for i in range(1, n + 1):            if d1[i] - d2[i] > 1:                ans = max(ans, d1[i])        return ans