Description

A company's org chart is given as a tree structure. Given two employees, find their common manager with the lowest rank. (The nearest common ancestor)

Input

Output

Constraints

• •All node values are unique
• •p and q always exist in tree
• •Number of nodes: 2 ~ 10,000

Examples

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

3

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

5