Think inductively. The first step is to get the root. Obviously, the root should be in pairs with all the nodes. If there isn't exactly one such node, then there are 0 ways.

The number of pairs involving a node must be less than or equal to that number of its parent.

Actually, if it's equal, then there is not exactly 1 way, because they can be swapped.

Recursively, given a set of nodes, get the node with the most pairs, then this must be a root and have no parents in the current set of nodes.