Lowest Common Ancestor (Binary Lifting)

Given a tree rooted at node 1, answer q queries, each asking for the lowest common ancestor of two nodes. Preprocess with binary lifting so each query takes O(log n).

1 <= n, q <= 10^5