← 返回题目列表

Codeforces · 1472/E

E. 正确放置

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

Polycarp邀请了$$$n$$$朋友来庆祝新年。庆祝活动期间,他决定和所有朋友拍一张合影。每个朋友都可以站在一边或侧躺。

每个朋友都有两个值 $$$h_i$$$ (他们的高度)和 $$$w_i$$$ (他们的宽度)。在照片上,第 $$$i$$$ 位朋友将占据一个矩形 $$$h_i \times w_i$$$ (如果他们站立)或 $$$w_i \times h_i$$$ (如果他们侧躺)。

如果第 $$$j$$$ 个朋友的矩形比第 $$$i$$$ 个朋友的矩形更低且更窄,则该第 $$$j$$$ 个朋友可以放置在照片上第 $$$i$$$ 个朋友的前面。正式而言,必须至少满足以下条件之一:

- $$$h_j < h_i$$$ 且 $$$w_j < w_i$$$ (两个朋友都站着或都在说谎);
- $$$w_j < h_i$$$ 且 $$$h_j < w_i$$$ (其中一个朋友站着,另一个朋友躺着)。

例如,如果 $$$n = 3$$$、$$$h=[3,5,3]$$$ 且 $$$w=[4,4,3]$$$,则:

- 第一个朋友可以放在第二个朋友的前面:$$$w_1 < h_2$$$ 和 $$$h_1 < w_2$$$ (其中一个是站着的,另一个是躺着的);
- 第三个朋友可以放在第二个朋友的前面:$$$h_3 < h_2$$$ 和 $$$w_3 < w_2$$$ (两个朋友都站着或都躺着)。

在其他情况下,前景中的人将与背景中的人重叠。

帮助Polycarp为每个$$$i$$$找到任意$$$j$$$,使得第$$$j$$$个朋友可以位于第$$$i$$$个朋友的前面(即至少满足上述条件之一)。

请注意,您不需要找到所有人的合影安排。您只需为每个朋友 $$$i$$$ 找到位于他前面的任何其他朋友 $$$j$$$ 即可。考虑一下,您需要解决 $$$n$$$ 个独立的子问题。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 朋友的数量。

接下来是 $$$n$$$ 行,每行都包含相应好友的描述。每个好友由两个整数 $$$h_i$$$ 和 $$$w_i$$$ ($$$1 \leq h_i, w_i \leq 10^9$$$) 分别描述第 $$$i$$$ 个好友的高度和宽度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出 $$$n$$$ 个整数,其中第 $$$i$$$ 个数字是可以放置在第 $$$i$$$ 前面的朋友的索引。如果没有这样的朋友,则输出-1。

如果有多个答案,则输出其中一个。

示例

输入 #1

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

输出 #1

-1 3 -1 
-1 -1 -1 
-1 -1 2 2 
3 3 -1 3

注意

语句中描述了第一个测试用例。

在第三个测试用例中,以下答案也是正确的:

- $$$[-1, -1, 1, 2]$$$;
- $$$[-1, -1, 1, 1]$$$;
- $$$[-1, -1, 2, 1]$$$.