# https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i
from typing import List

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        road = [[i + 1] for i in range(n - 1)]
        result = []
        def recurse(memo, curr = 0):
            if curr >= n -1:
                return 0
            if memo[curr] != -1:
                return memo[curr]
            memo[curr] = min(n, *[recurse(memo, dest) + 1 for dest in road[curr]])
            return memo[curr]

        for [start, end] in queries:
            memo = [-1] * (n -1)
            road[start].append(end)
            result.append(recurse(memo))
        return result