Program

Time limit2sMemory limit512 MB

Summary

Given a sequence of assignment and conditional assignment instructions starting from X=1, delete the fewest instructions so the final value is k, for every k.

Level: Hard8 of 10
Topics: Graph, Shortest path, BFS, Implementation
Solved: No attempts yet

Problem

You are given a program that operates on an integer variable $X$ , which is initially equal to 1. The program consists of $n$ instructions of two types:

1 p ( $1 \le p \le n$ ) assigns the value $p$ to variable $X$ .
2 p q ( $1 \le p, q \le n$ , $p \neq q$ ) assigns the 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 cannot reorder instructions or add new instructions. What is the minimum number of steps required to get a program that, after it runs, leaves variable $X$ with the value $k$ ? Solve this problem for each $k$ from 1 to $n$ .

Input

The first line of input contains a single integer $n$ ( $2 \le n \le 10^6$ ), the number of instructions in the program.

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

Output

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

Examples2

Example 1
Input
```
3
1 1
1 2
1 3
```
Expected output
```
2 1 0
```
Example 2
Input
```
4
2 1 2
1 3
2 2 3
2 3 1
```
Expected output
```
0 2 1 -1
```