字典序最小的排列

题目描述

给定 $(1, 2, \ldots, N)$ 的两个排列 $P = (P_1, P_2, \ldots, P_N)$ 和 $A = (A_1, A_2, \ldots, A_N)$。

你可以进行任意次（可以为 0 次）如下操作：

对所有 $i = 1, 2, \ldots, N$，同时将 $A_i$ 替换为 $A_{P_i}$。

请输出可以获得的最小字典序的 $A$。

什么是字典序？

对于长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$，当且仅当存在整数 $i\ (1 \le i \le N)$ 使得 $A_i \lt B_i$，并且对所有 $1 \le j \lt i$ 有 $A_j = B_j$ 时，称 $A$ 的字典序小于 $B$。

输入格式

输入按以下格式从标准输入给出：

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

设 $(A_1, A_2, \ldots, A_N)$ 为可以获得的最小字典序的 $A$。在一行中按顺序用空格隔开输出 $A_1, A_2, \ldots, A_N$。

样例

6
3 1 5 6 2 4
4 3 1 6 2 5

1 4 2 5 3 6

最初 $A = (4, 3, 1, 6, 2, 5)$。

重复进行该操作会得到如下结果：

$A = (1, 4, 2, 5, 3, 6)$

$A = (2, 1, 3, 6, 4, 5)$

$A = (3, 2, 4, 5, 1, 6)$

$A = (4, 3, 1, 6, 2, 5)$

之后每四次操作 $A$ 都会恢复原状。

因此，输出其中字典序最小的 $1\ 4\ 2\ 5\ 3\ 6$。

8
3 5 8 7 2 6 1 4
1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

也可以选择不进行任何操作。

26
24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10
15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17

4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le P_i \le N\ (1 \le i \le N)$
• $P_i \neq P_j\ (1 \le i \lt j \le N)$
• $1 \le A_i \le N\ (1 \le i \le N)$
• $A_i \neq A_j\ (1 \le i \lt j \le N)$
• 输入中的所有数值均为整数