class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<Integer>[] g = new ArrayList[n - 1];
        Arrays.setAll(g, i -> new ArrayList<>());
        for(int i = 0; i < n - 1; i ++ ) 
            g[i].add(i + 1);

        int[] ans = new int[queries.length];
        int[] v = new int[n - 1];
        for(int i = 0; i < queries.length; i ++ )
        {
            g[queries[i][0]].add(queries[i][1]);
            ans[i] = bfs(i + 1, g, v, n);
        }

        return ans;
    }

    public int bfs(int i, List<Integer>[] g, int[] v, int n)
    {
        ArrayList<Integer> q = new ArrayList<>();
        q.add(0);

        for(int step = 1; ; step ++ )
        {
            ArrayList<Integer> tmp = q;
            q = new ArrayList<>();

            for(int x: tmp)
            {
                for(int y: g[x])
                {
                    if(y == n - 1) return step;
                    if(v[y] != i)
                    {
                        v[y] = i;
                        q.add(y);
                    }
                }
            }
        }
    }
}