Selling a Menagerie
Description
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).
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 $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.
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.
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