Lowest Common Ancestor in an N-ary Tree (Return the Ancestor)

Problem You are given an N-ary tree (each node can have 0..many children) and two nodes u and v from the tree. Determine whether u and v have a common ancestor, and return their Lowest Common Ancestor (LCA). If an LCA exists, return that ancestor node. If either node is not in the tree, or no common ancestor exists (e.g., invalid input), return null. Suggested Input Format First line: integer n, number of nodes. Next n lines: each line parent child describes one parent->child edge. The root has parent -1. Last line: two integers u v. Output Print the LCA node id; print null if it does not exist. Constraints 1 <= n <= 2e5 Examples edges: (-1,1),(1,2),(1,3),(3,4), query 2 4 => output 1 edges: (-1,1),(1,2),(1,3), query 2 3 => output 1 edges: (-1,1),(1,2), query 2 99 => output null Example Input 5 -1 1 1 2 1 3 3 4 4 5 2 5 Output 1