시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 13 10 7 70.000%

문제

You are given a program operating with integer variable X, which is initially equal to 1. The program consists of n instructions of two types:

  • “1 p” (1 ≤ p ≤ n), assigns value p to variable X.
  • “2 p q” (1 ≤ p, q ≤ n, p 6= q), assigns value q to variable X only if the current value of X is p.

In one step, you can remove any single instruction from the program. You can’t reorder instructions or add new instructions. What is the minimum number of steps required to get such a program that, after it runs, the variable X has value k? You are asked to solve this problem for each k from 1 to n.

입력

The first line of input contains a single integer n (2 ≤ n ≤ 106), the number of instructions in program.

The next n lines contains descriptions of instructions in the format described above.

출력

Output n integers, where i-th integer is the minimum number of steps required to make program set value i to variable X, or −1 if it is impossible.

예제 입력 1

3
1 1
1 2
1 3

예제 출력 1

2 1 0

예제 입력 2

4
2 1 2
1 3
2 2 3
2 3 1

예제 출력 2

0 2 1 -1