310697: CF1872F. Selling a Menagerie

F. Selling a Menagerietime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are the owner of a menagerie consisting of $n$ animals numbered from $1$ to $n$. However, maintaining the menagerie is quite expensive, so you have decided to sell it!

It is known that each animal is afraid of exactly one other animal. More precisely, animal $i$ is afraid of animal $a_i$ ($a_i \neq i$). Also, the cost of each animal is known, for animal $i$ it is equal to $c_i$.

You will sell all your animals in some fixed order. Formally, you will need to choose some permutation$^\dagger$ $p_1, p_2, \ldots, p_n$, and sell animal $p_1$ first, then animal $p_2$, and so on, selling animal $p_n$ last.

When you sell animal $i$, there are two possible outcomes:

• If animal $a_i$ was sold before animal $i$, you receive $c_i$ money for selling animal $i$.
• If animal $a_i$ was not sold before animal $i$, you receive $2 \cdot c_i$ money for selling animal $i$. (Surprisingly, animals that are currently afraid are more valuable).

Your task is to choose the order of selling the animals in order to maximize the total profit.

For example, if $a = [3, 4, 4, 1, 3]$, $c = [3, 4, 5, 6, 7]$, and the permutation you choose is $[4, 2, 5, 1, 3]$, then:

• The first animal to be sold is animal $4$. Animal $a_4 = 1$ was not sold before, so you receive $2 \cdot c_4 = 12$ money for selling it.
• The second animal to be sold is animal $2$. Animal $a_2 = 4$ was sold before, so you receive $c_2 = 4$ money for selling it.
• The third animal to be sold is animal $5$. Animal $a_5 = 3$ was not sold before, so you receive $2 \cdot c_5 = 14$ money for selling it.
• The fourth animal to be sold is animal $1$. Animal $a_1 = 3$ was not sold before, so you receive $2 \cdot c_1 = 6$ money for selling it.
• The fifth animal to be sold is animal $3$. Animal $a_3 = 4$ was sold before, so you receive $c_3 = 5$ money for selling it.

Your total profit, with this choice of permutation, is $12 + 4 + 14 + 6 + 5 = 41$. Note that $41$ is not the maximum possible profit in this example.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but $4$ is present in the array).

Input

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case description contains an integer $n$ ($2 \le n \le 10^5$) — the number of animals.

The second line of the test case description contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \neq i$) — $a_i$ means the index of the animal that animal $i$ is afraid of.

The third line of the test case description contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of the animals.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

Output $t$ lines, each containing the answer to the corresponding test case. The answer should be $n$ integers — the permutation $p_1, p_2, \ldots, p_n$, indicating in which order to sell the animals in order to maximize the profit. If there are multiple possible answers, you can output any of them.

ExampleInput

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

Output

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

题目大意：
你拥有一个由n只动物组成的动物园，动物编号从1到n。每只动物都害怕另一只特定的动物，即动物i害怕动物a_i（a_i ≠ i）。每只动物的价值也已知，动物i的价值为c_i。你需要以某种顺序卖出所有动物，形式上，你需要选择一个排列p_1, p_2, …, p_n，并按照这个顺序卖出动物。卖出动物i时，有两种可能的结果：
1. 如果动物a_i在动物i之前被卖出，你将获得c_i的价值。
2. 如果动物a_i没有在动物i之前被卖出，你将获得2 * c_i的价值。
你的任务是选择卖出动物的顺序，以最大化总利润。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数n（2 ≤ n ≤ 10^5），表示动物的数量。
- 第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n，a_i ≠ i），a_i表示动物i害怕的动物的索引。
- 第三行包含n个整数c_1, c_2, …, c_n（1 ≤ c_i ≤ 10^9），表示动物的价值。

输出：
- 对于每个测试用例，输出一行，包含n个整数，表示卖出动物的顺序，以最大化利润。如果有多个可能的答案，你可以输出其中任何一个。题目大意： 你拥有一个由n只动物组成的动物园，动物编号从1到n。每只动物都害怕另一只特定的动物，即动物i害怕动物a_i（a_i ≠ i）。每只动物的价值也已知，动物i的价值为c_i。你需要以某种顺序卖出所有动物，形式上，你需要选择一个排列p_1, p_2, …, p_n，并按照这个顺序卖出动物。卖出动物i时，有两种可能的结果： 1. 如果动物a_i在动物i之前被卖出，你将获得c_i的价值。 2. 如果动物a_i没有在动物i之前被卖出，你将获得2 * c_i的价值。 你的任务是选择卖出动物的顺序，以最大化总利润。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数n（2 ≤ n ≤ 10^5），表示动物的数量。 - 第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n，a_i ≠ i），a_i表示动物i害怕的动物的索引。 - 第三行包含n个整数c_1, c_2, …, c_n（1 ≤ c_i ≤ 10^9），表示动物的价值。 输出： - 对于每个测试用例，输出一行，包含n个整数，表示卖出动物的顺序，以最大化利润。如果有多个可能的答案，你可以输出其中任何一个。