Lowest common ancestor | Terminal43 Code

Mobile coding works. A laptop is faster for long sessions.

Problem

A tree with n nodes numbered from 1 to n is represented by

the parent array t, where t[i] is the parent of node i, and

t[i] = 0 means that node i is the root of the tree.

Two nodes x and y are also read (not necessarily distinct). Print

the lowest common ancestor of x and y: the deepest node that

appears on both the path from x to the root and the path from y

to the root.

Convention: a node is its own ancestor. If x = y, the answer is x.

If x is an ancestor of y, the answer is x.

Input format

Input input.txt

The first line contains three natural numbers `n`, `x`, and `y`, separated by spaces. The second line contains the `n` values of the parent array, separated by spaces. - `1 <= n <= 100` - `1 <= x, y <= n` - the array describes a valid tree

Output format

Output output.txt

The program prints a single natural number: the index of the lowest common ancestor of nodes `x` and `y`.

Example

input

7 1 6

2 4 4 0 4 5 5

output

Sample cases (from the problem)

Sample Case 1

Input

7 1 6

2 4 4 0 4 5 5

Expected output

Ready to solve this challenge?

Create a free account to write code, submit solutions, and track your progress.

🔍 Interactive Debugger

0 / 0

Analyzing your code...

Problem

Input format

Output format

Example

Stuck?

💬 Discussion

Sample cases (from the problem)

Solve it your way first

Ready to solve this challenge?

🔍 Interactive Debugger

Error

Problem

Input format

Output format

Example

Stuck?

💬 Discussion

Sample cases (from the problem)

Solve it your way first

Ready to solve this challenge?

⌨️ Keyboard Shortcuts

🔍 Interactive Debugger

Error