#P1872F. Selling a Menagerie

    ID: 8443 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>dfs and similardsugraphsimplementationmath*1800

Selling a Menagerie

Description

You are the owner of a menagerie consisting of nn animals numbered from 11 to nn. 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 ii is afraid of animal aia_i (aiia_i \neq i). Also, the cost of each animal is known, for animal ii it is equal to cic_i.

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

When you sell animal ii, there are two possible outcomes:

  • If animal aia_i was sold before animal ii, you receive cic_i money for selling animal ii.
  • If animal aia_i was not sold before animal ii, you receive 2ci2 \cdot c_i money for selling animal ii. (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]a = [3, 4, 4, 1, 3], c=[3,4,5,6,7]c = [3, 4, 5, 6, 7], and the permutation you choose is [4,2,5,1,3][4, 2, 5, 1, 3], then:

  • The first animal to be sold is animal 44. Animal a4=1a_4 = 1 was not sold before, so you receive 2c4=122 \cdot c_4 = 12 money for selling it.
  • The second animal to be sold is animal 22. Animal a2=4a_2 = 4 was sold before, so you receive c2=4c_2 = 4 money for selling it.
  • The third animal to be sold is animal 55. Animal a5=3a_5 = 3 was not sold before, so you receive 2c5=142 \cdot c_5 = 14 money for selling it.
  • The fourth animal to be sold is animal 11. Animal a1=3a_1 = 3 was not sold before, so you receive 2c1=62 \cdot c_1 = 6 money for selling it.
  • The fifth animal to be sold is animal 33. Animal a3=4a_3 = 4 was sold before, so you receive c3=5c_3 = 5 money for selling it.

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

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

The first line of the input contains an integer tt (1t1041 \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 nn (2n1052 \le n \le 10^5) — the number of animals.

The second line of the test case description contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n, aiia_i \neq i) — aia_i means the index of the animal that animal ii is afraid of.

The third line of the test case description contains nn integers c1,c2,,cnc_1, c_2, \dots, c_n (1ci1091 \le c_i \le 10^9) — the costs of the animals.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

Output tt lines, each containing the answer to the corresponding test case. The answer should be nn integers — the permutation p1,p2,,pnp_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 tt (1t1041 \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 nn (2n1052 \le n \le 10^5) — the number of animals.

The second line of the test case description contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n, aiia_i \neq i) — aia_i means the index of the animal that animal ii is afraid of.

The third line of the test case description contains nn integers c1,c2,,cnc_1, c_2, \dots, c_n (1ci1091 \le c_i \le 10^9) — the costs of the animals.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

Output

Output tt lines, each containing the answer to the corresponding test case. The answer should be nn integers — the permutation p1,p2,,pnp_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.

样例输入 1

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

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