eolymp
bolt
Try our new interface for solving problems
Problems

Изоморфизм деревьев

Изоморфизм деревьев

Даны два дерева, состоящие из \textbf{N} узлов. Деревья называются \textit{изоморфными}, если они имеют одинаковую структуру. Более точно, деревья \textbf{A} и \textbf{B} - изоморфны, если существует такая перестановка \textbf{p = (p_1, ..., p_N)}, что вершина\textbf{i} является корнем в дереве \textbf{A} тогда и только тогда, когда вершина \textbf{p_i} - корень дерева \textbf{B}, а вершина \textbf{i} является родительской для \textbf{j} в дереве \textbf{A} тогда и только тогда, когда \textbf{p_i} является родительской для \textbf{p_j} в дерев \textbf{B}. \InputFile В первой строке входного файла задаётся натуральное число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}). Во второй и третьей строках задаются деревья. Каждая из этих строк содержит по \textbf{N} чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_N}, где \textbf{a_i} определяет номер родительской вершины для вершины \textbf{i} или равно \textbf{0}, если вершина \textbf{i} является корнем. \OutputFile В выходной файл необходимо вывести \textbf{N} чисел, определяющих перестановку-изоморфизм \textbf{p}, переводящую первое дерево во второе. Если таких перетсановок несколько, можно выводить любую из них. Если деревья неизоморфны между собой, выведите одно число \textbf{-1}.
Time limit 1 second
Memory limit 256 MiB
Input example #1
4
0 1 1 3
4 4 1 0
Output example #1
4 2 1 3
Source III International Summer School Programming in Sevastopol 2012