class Solution:

    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:

        graph, ans = [[i+1] for i in range(n)], []

        

        def bfs():

            dist = [0 for _ in range(n)]

            queue = deque([0])

            dist[0] = 1

            while dist[-1] == 0:

                cur = queue.popleft()

                for adj in graph[cur]:

                    if dist[adj] == 0:

                        dist[adj] = dist[cur] + 1

                        queue.append(adj)

            return dist[-1] - 1

        

        for query in queries:

            graph[query[0]].append(query[1])

            ans.append(bfs())

        

        return ans


뭘 원한걸까? 정말 BFS 500번을 원한걸까?

기존의 결과를 이용해서 쿼리마다 효율적으로 값을 업데이트하는 방법이 있을텐데..