Ізоморфізм дерев#3680

Ізоморфізм дерев

1 секунда
256 мегабайтів
Легка

Дано два дерева, кожне з яких складається з вузлів. Дерева називаються ізоморфними, якщо вони мають однакову структуру.

Точніше, дерева і є ізоморфними, якщо існує така перестановка p = (p_1, \ldots, p_N), що вершина є коренем у дереві тоді і тільки тоді, коли вершина p_i є коренем у дереві , а вершина є батьківською для у дереві тоді і тільки тоді, коли p_i є батьківською для p_j у дереві .

Вхідні дані

У першому рядку вхідного файлу задано натуральне число (1 \leq N \leq 10^5). У другому і третьому рядках описані дерева. Кожен з цих рядків містить чисел a_1, a_2, \ldots, a_N, де a_i вказує на номер батьківської вершини для вершини або дорівнює , якщо вершина є коренем.

Вихідні дані

У вихідний файл потрібно вивести чисел, що визначають перестановку-ізоморфізм , яка перетворює перше дерево у друге. Якщо таких перестановок декілька, можна вивести будь-яку з них. Якщо дерева не є ізоморфними, виведіть одне число .

Приклади

Приклад 1

Loading
Loading