프로그램

시간 제한2초메모리 제한512 MB

요약

X=1에서 시작해 대입과 조건부 대입 명령으로 이루어진 프로그램이 주어질 때, 마지막 값이 k가 되도록 지워야 할 최소 명령 수를 모든 k에 대해 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 최단 경로, BFS, 구현
정답자: 아직 제출이 없습니다

문제

정수 변수 $X$ 를 사용하는 프로그램이 있다. 처음에 $X = 1$ 이다. 프로그램은 두 종류의 명령 $n$ 개로 이루어진다.

1 p ( $1 \le p \le n$ ): 변수 $X$ 에 값 $p$ 를 대입한다.
2 p q ( $1 \le p, q \le n$ , $p \neq q$ ): 현재 $X$ 의 값이 $p$ 일 때만 변수 $X$ 에 값 $q$ 를 대입한다.

한 단계에서 프로그램의 명령 하나를 골라 지울 수 있다. 명령의 순서를 바꾸거나 새 명령을 추가할 수는 없다. 프로그램을 실행한 뒤 변수 $X$ 의 값이 $k$ 가 되도록 만들기 위해 필요한 최소 단계 수는 얼마인가? 이 문제를 $k = 1$ 부터 $n$ 까지 각각에 대해 해결하라.

입력

첫째 줄에 프로그램의 명령 개수 $n$ 이 주어진다. ( $2 \le n \le 10^6$ )

다음 $n$ 개 줄에 위에 설명한 형식으로 명령이 하나씩 주어진다.

출력

$n$ 개의 정수를 출력한다. $i$ 번째 정수는 프로그램이 변수 $X$ 에 값 $i$ 를 대입하도록 만들기 위해 필요한 최소 단계 수이며, 불가능하면 $-1$ 이다.

예제2

예제 1
입력
```
3
1 1
1 2
1 3
```
예상 출력
```
2 1 0
```
예제 2
입력
```
4
2 1 2
1 3
2 2 3
2 3 1
```
예상 출력
```
0 2 1 -1
```