#P1872F. Selling a Menagerie
Selling a Menagerie
Description
You are the owner of a menagerie consisting of animals numbered from to . 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 is afraid of animal (). Also, the cost of each animal is known, for animal it is equal to .
You will sell all your animals in some fixed order. Formally, you will need to choose some permutation , and sell animal first, then animal , and so on, selling animal last.
When you sell animal , there are two possible outcomes:
- If animal was sold before animal , you receive money for selling animal .
- If animal was not sold before animal , you receive money for selling animal . (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 , , and the permutation you choose is , then:
- The first animal to be sold is animal . Animal was not sold before, so you receive money for selling it.
- The second animal to be sold is animal . Animal was sold before, so you receive money for selling it.
- The third animal to be sold is animal . Animal was not sold before, so you receive money for selling it.
- The fourth animal to be sold is animal . Animal was not sold before, so you receive money for selling it.
- The fifth animal to be sold is animal . Animal was sold before, so you receive money for selling it.
Your total profit, with this choice of permutation, is . Note that is not the maximum possible profit in this example.
A permutation of length is an array consisting of distinct integers from to in any order. For example, is a permutation, but is not a permutation ( appears twice in the array) and is also not a permutation (, but is present in the array).
The first line of the input contains an integer () — the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case description contains an integer () — the number of animals.
The second line of the test case description contains integers (, ) — means the index of the animal that animal is afraid of.
The third line of the test case description contains integers () — the costs of the animals.
It is guaranteed that the sum of over all test cases does not exceed .
Output lines, each containing the answer to the corresponding test case. The answer should be integers — the permutation , 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 () — the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case description contains an integer () — the number of animals.
The second line of the test case description contains integers (, ) — means the index of the animal that animal is afraid of.
The third line of the test case description contains integers () — the costs of the animals.
It is guaranteed that the sum of over all test cases does not exceed .
Output
Output lines, each containing the answer to the corresponding test case. The answer should be integers — the permutation , 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.