According to the given definition of a directed tree, the root must only have edges going out of it. And there is only one such node in the entire tree.

So when we add the edges one by one, we’ll be having a forest initially, which eventually converges to a single tree. Each tree in the current forest can be uniquely identified by the special root node (which has in-degree 0, i.e., no incoming edges to this node).

When merging, we will merge two trees, and the root node of the new tree will be one of the roots of the old trees. Out of the two old roots, the new root can be identified by the direction of the edge being added. If the new edge is connecting a node from tree2 to tree1, then the new root of the combined tree will be the root of tree1.

During this process of merging, if we add an edge within a tree (that is two nodes have the same parent in the DSU), then this is the extra edge.

@vai53, did you understand this approach?