Distance between two nodes

Problem

Print the number of links on the route between two nodes of the tree. A route may go up and then down. All values are different and both nodes are in the tree. If both values are the same, the distance is 0.

Input, output and limits

Input: Line 1: the tree in level order, values separated by spaces, with null for a missing child. Line 2: two values p and q that are in the tree.
Output: One integer: the number of links between them.
Constraints: 1 ≤ number of nodes ≤ 3000
All values are different integers between 1 and 100000

Examples

Example 1

Input

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

Output

5 to 3 to 1 is 2 links.

Example 2

Input

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

Output

7 to 2 to 4 is 2 links.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Find the lowest common ancestor first.

Hint 2

The distance is the distance from it to p plus the distance from it to q.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Trees problems

Problem

Input, output and limits

Examples

Hints

More Binary Trees problems