CareerCup

Given an N-ary tree with thousands of nodes, pair the leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have a common edge that was used in a previous pairing.
For example,
A
/ | \
B C D
/ / | \
E F G H
Leaf nodes: E, F, G, H & D

Possible Pairs in O/Ps:
a) (E-F), (G-H) or
b) (E-G), (F-H) or
c) (E-H), (F-G) or
d) (E-D), (F-G) or
e) (E-D), (G-H) or
f) (E-D), (F-H) or
g) (D-H), (F-G) or
h) (D-G), (F-H) or
i) (D-F), (G-H)
Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.

i.e. E-B-A-C-F —> (E-F) pair
D-A-C-G —> (D-G) pair
D-A-C-H —> (D-H) pair
So the above case is NOT possible