F. Продажа зверинца
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы владелец зверинца, состоящего из $$$n$$$ животных пронумерованных от $$$1$$$ до $$$n$$$. Однако содержать зверинец достаточно затратно, поэтому вы решили его продать!

Известно, что каждое животное боится ровно одного другого животного. А точнее, животное $$$i$$$ боится животного $$$a_i$$$ ($$$a_i \neq i$$$). Также для каждого животного известна его стоимость, для животного $$$i$$$ она равняется $$$c_i$$$.

Вы будете продавать всех своих животных в каком-то зафиксированном порядке. Формально, вам надо будет выбрать некоторую перестановку$$$^\dagger$$$ $$$p_1, p_2, \ldots, p_n$$$, и продать сначала животное $$$p_1$$$, потом животное $$$p_2$$$, и так далее, последним продав животное $$$p_n$$$.

Когда вы продаёте животное $$$i$$$, есть два варианта развития событий:

  • Если животное $$$a_i$$$ было продано раньше чем животное $$$i$$$, вы получаете $$$c_i$$$ денег за продажу животного $$$i$$$.
  • Если животное $$$a_i$$$ не было продано раньше чем животное $$$i$$$, вы получаете $$$2 \cdot c_i$$$ денег за продажу животного $$$i$$$. (Удивительно, но животные, которые боятся в текущий момент имеют большую ценность).

Ваша задача — выбрать порядок продажи животных так, чтобы максимизировать суммарную прибыль.

Например, если $$$a = [3, 4, 4, 1, 3]$$$, $$$c = [3, 4, 5, 6, 7]$$$ и выбранная вами перестановка равна $$$[4, 2, 5, 1, 3]$$$, то:

  • Первым продаётся животное $$$4$$$. Животное $$$a_4 = 1$$$ не было продано ранее, а значит, вы получаете $$$2 \cdot c_4 = 12$$$ денег за продажу.
  • Вторым продаётся животное $$$2$$$. Животное $$$a_2 = 4$$$ было продано ранее, а значит, вы получаете $$$c_2 = 4$$$ денег за продажу.
  • Третьим продаётся животное $$$5$$$. Животное $$$a_5 = 3$$$ не было продано ранее, а значит, вы получаете $$$2 \cdot c_5 = 14$$$ денег за продажу.
  • Четвёртым продаётся животное $$$1$$$. Животное $$$a_1 = 3$$$ не было продано ранее, а значит, вы получаете $$$2 \cdot c_1 = 6$$$ денег за продажу.
  • Пятым продаётся животное $$$3$$$. Животное $$$a_3 = 4$$$ было продано ранее, а значит, вы получаете $$$c_3 = 5$$$ денег за продажу.

Ваша суммарная прибыль при таком выборе перестановки, равна $$$12 + 4 + 14 + 6 + 5 = 41$$$. Обратите внимание, что $$$41$$$ — не максимально возможная прибыль в этом примере.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но в массиве присутствует $$$4$$$).

Входные данные

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество животных.

Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq i$$$) — $$$a_i$$$ означает номер животного, которого боится животное $$$i$$$.

Третья строка набора входных данных содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — стоимости животных.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$10^5$$$.

Выходные данные

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите $$$n$$$ целых чисел — перестановку $$$p_1, p_2, \ldots, p_n$$$, обозначающую, в каком порядке нужно продавать животных, чтобы максимизировать прибыль. Если есть несколько возможных ответов, можно вывести любой из них.

Пример
Входные данные
8
3
2 3 2
6 6 1
8
2 1 4 3 6 5 8 7
1 2 1 2 2 1 2 1
5
2 1 1 1 1
9 8 1 1 1
2
2 1
1000000000 999999999
7
2 3 2 6 4 4 3
1 2 3 4 5 6 7
5
3 4 4 1 3
3 4 5 6 7
3
2 1 1
1 2 2
4
2 1 4 1
1 1 1 1
Выходные данные
1 2 3
2 4 5 1 6 3 7 8
3 4 5 1 2
1 2
7 5 1 3 2 6 4
5 3 2 4 1
3 2 1
3 4 1 2