Codeforces Round 693 (Div. 3) |
---|
Закончено |
Поликарп пригласил $$$n$$$ друзей на встречу Нового года. Во время торжества он решил сделать общую фотографию всех своих друзей. Каждый друг может стоять или лечь на бок.
Каждый друг характеризуется двумя значениями $$$h_i$$$ (его рост) и $$$w_i$$$ (его ширина). На фото $$$i$$$-й друг будет занимать прямоугольник $$$h_i \times w_i$$$ (если он стоит) или $$$w_i \times h_i$$$ (если он лежит).
Друга с номером $$$j$$$ можно разместить перед $$$i$$$-м другом на фотографии, если его прямоугольник ниже и уже, чем прямоугольник $$$i$$$-го друга. Формально должно быть выполнено хотя бы одно из следующих условий:
Например, если $$$n = 3$$$, $$$h=[3,5,3]$$$ и $$$w=[4,4,3]$$$, то:
В других случаях человек на переднем плане будет перекрывать человека на заднем плане.
Помогите Поликарпу для каждого $$$i$$$ найти любой $$$j$$$, такой, что перед $$$i$$$-м другом может быть расположен $$$j$$$-й друг (т.е. хотя бы одно из условий выше было выполнено).
Обратите внимание, что вам не нужно находить расположение всех людей для общей фотографии. Вам нужно, чтобы каждый друг $$$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.
Если существует несколько ответов, выведите любой.
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 3 -1 -1 -1 -1 -1 -1 2 2 3 3 -1 3
Первый набор входных данных разобран в условии.
Во третьем наборе входных данных следующие варианты ответы тоже являются верными:
Название |
---|