Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$" In this version of the problem, the queries are on-line. Interspersed with the queries are on-line commands of two types: $link(x, y)$, where $y$ but not necessarily $x$ is a tree root, and $cut (x)$, where $x$ is not a root. The effect of a command $link(x, y)$ is to combine the trees containing $x$ and $y$ by making $x$ the parent of $y$. The effect of a command $cut (x)$ is to cut the edge connecting $x$ and its parent, splitting the tree containing $x$ into two trees: one containing all descendants of $x$ and another containing all nondescendants of $x$.