← 返回题目列表

AtCoder · acl1_a

A. 可到达的城镇

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 二维平面上的城市。的坐标 i第城市是 (x_i, y_i)。这里 (x_1, x_2, \dots, x_N) 和 (y_1, y_2, \dots, y_N) 都是排列 (1, 2, \dots, N).

对于每个 k = 1,2,\dots,N,找到以下问题的答案:

Rng 在城市 k。 Rng 可以任意多次执行以下移动:

  • 搬到另一个拥有较小规模的城市 x- 坐标和更小的 y- 坐标,或更大 x- 坐标和更大的 y- 坐标,比他当前所在的城市。

有多少个城市(包括市 k) 可从城市到达 k?

约束

  • 1 \leq N \leq 200,000
  • (x_1, x_2, \dots, x_N) 是一个排列 (1, 2, \dots, N).
  • (y_1, y_2, \dots, y_N) 是一个排列 (1, 2, \dots, N).
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
:
x_N y_N

输出

打印 N 行。在 i- 第行打印问题的答案 k = i.


示例输入 1

4
1 4
2 3
3 1
4 2

示例输出 1

1
1
2
2

Rng可以到达City 4 来自城市 3,或相反城市 3 来自城市 4.


示例输入 2

7
6 4
4 3
3 5
7 1
2 7
5 2
1 6

示例输出 2

3
3
1
1
2
3
2