#include <bits/stdc++.h>
using namespace std;
struct node {
int val;
node *left, *right;
};
node *lca(node *root, node *p, node *q) {
if (!root || root==q || root==q) return root;
auto left = lca(root->left, p, q);
auto right = lca(root->right, p, q);
if (!left) return right;
if (!right) return left;
return root;
}