// to run:
// dfsSZ(0, -1, 0);
// dfsHLD(0, -1, 0);
//
// [tin[x], tout[x]] --- subtree of x
// [tin[TO[x]], tin[x]] --- path from TO[x] to x

VI g[MAX];     // graph
int SZ[MAX];   // size of the subtree
int H[MAX];    // height of the vertex
int P[MAX];    // parent of the vertex
int TO[MAX];   // top node of the heavy path
int tin[MAX];
int tout[MAX];
int timer = 0;

void dfsSZ(int x, int p, int h)
{
    SZ[x] = 1;
    H[x] = h;
    P[x] = p;
    FOR (i, 0, SZ(g[x]))
    {
        int to = g[x][i];
        if (to == p) continue;

        dfsSZ(to, x, h + 1);
        SZ[x] += SZ[to];
        if (g[x][0] == p || SZ[to] > SZ[g[x][0]])
        {
            swap(g[x][0], g[x][i]);
        }
    }
}

void dfsHLD(int x, int p, int v)
{
    tin[x] = timer++;
    TO[x] = v;
    FOR (i, 0, SZ(g[x]))
    {
        int to = g[x][i];
        if (to == p) continue;
        if (i == 0) dfsHLD(to, x, v);
        else dfsHLD(to, x, to);
    }
    tout[x] = timer - 1;
}

int get(int x, int y) // query on path x-y
{
    int res = 0;
    while(true)
    {
        int tx = TO[x];
        int ty = TO[y];
        if (tx == ty) // same heavy path
        {
            int t1 = tin[x];
            int t2 = tin[y];
            if (t1 > t2) swap(t1, t2);
            if (t1 < t2)
            {
                res = max(res, R.get(t1 + 1, t2)); // lca not considered
            }
            break;
        }

        if (H[tx] < H[ty])
        {
            swap(tx, ty);
            swap(x, y);
        }

        res = max(res, R.get(tin[tx], tin[x]));
        x = P[tx];
    }
    return res;
}