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 $link(x, y)$ such that $y$, but not necessarily $x$, is a tree 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$.