CodeCoder 대 TopForces

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

요약

두 사이트 중 적어도 하나에서 더 높은 점수를 가진 사람으로 이어지는 경로를 따라 도달할 수 있는 사람 수를 각자 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, 정렬, DFS, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

바이트랜드에서는 프로그래밍 대회가 인기가 많다. 바이트랜드 시민은 모두 CodeCoder와 TopForces라는 두 채점 사이트에 등록되어 있다. 두 사이트는 각각 독자적인 레이팅 체계를 운영한다. 각 사이트에서 시민마다 실력을 나타내는 정수 레이팅이 하나씩 정해져 있고, 같은 사이트에서 레이팅이 같은 시민은 없다. 레이팅이 높을수록 실력이 좋다.

바이트랜드 시민은 낙천적이다. 시민 $A$ 는 다음 조건을 만족하는 시민 수열 $A = P_0, P_1, \ldots, P_k = B$ ( $k \ge 1$ )가 존재하면 대회에서 시민 $B$ 를 이길 가능성이 있다고 생각한다. 모든 $i$ ( $0 \le i < k$ )에 대해 $P_i$ 가 두 사이트 중 적어도 한 곳에서 $P_{i+1}$ 보다 레이팅이 높다.

각 시민이 자기 자신을 뺀 몇 명을 이길 가능성이 있다고 생각하는지 구하라.

입력

첫째 줄에 시민 수 $n$ 이 주어진다 ( $1 \le n \le 100\,000$ ).

다음 $n$ 개 줄 중 $i$ 번째 줄에는 $i$ 번 시민의 CodeCoder 레이팅 $CC_i$ 와 TopForces 레이팅 $TF_i$ 가 주어진다 ( $1 \le CC_i, TF_i \le 10^6$ ). 각 사이트의 레이팅 $n$ 개는 모두 서로 다르다.

출력

$n$ 개 줄을 출력한다. $i$ 번째 줄에는 $i$ 번 시민이 이길 가능성이 있다고 생각하는 다른 시민의 수 $b_i$ 를 출력한다. 입력에 주어진 순서대로 출력한다.

예제5

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

예제 5

입력

3
1 1000000
500000 500000
1000000 1

예상 출력

2
2
2