Description

Please implement the conversion between a Prüfer sequence and an unrooted tree.

To make implementation easier, although the tree is unrooted, when reading the input we still treat $n$ as its root.

For an unrooted tree, let $f_{1 \dots n-1}$ be its parent sequence ($f_i$ denotes the parent of node $i$ when rooting the tree at $n$), and let $p_{1 \dots n-2}$ be its Prüfer sequence.

In addition, for a sequence $a_{1 \dots m}$ of length $m$, define its value as $\operatorname{xor}_{i = 1}^m i \times a_i$.

Input Format

The first line contains two integers $n, m$, representing the number of nodes in the tree and the conversion type.

If $m = 1$, the second line contains $n - 1$ integers, representing the parent sequence.
If $m = 2$, the second line contains $n - 2$ integers, representing the Prüfer sequence.

Output Format

If $m = 1$, output one integer on a single line, representing the value of the Prüfer sequence corresponding to the given parent sequence.
If $m = 2$, output one integer on a single line, representing the value of the parent sequence corresponding to the given Prüfer sequence.

6 1
3 6 4 6 1

29

6 2
4 6 5 2

4

Hint

[Sample 1 Explanation]

$p = \{6\ 1\ 3\ 4\}$.

[Sample 2 Explanation]

$f = \{4\ 6\ 6\ 5\ 2\}$.

[Constraints]

Translated by ChatGPT 5