Let us choose an arbitrary node ~r~ to be the root of some tree. Let us denote with ~p_x~ the total XOR of all the curiosities on the path from node ~r~ to node ~x~. It can be easily seen that a pair of planets ~x, y~ is boring if and only if it holds ~p_x \mathbin{XOR} p_y = 0 \iff p_x = p_y~.

Let us notice that we can "reverse" the input data so, instead of destroying the paths, we can add them.

For connecting the components we will use the union-find algorithm where we will, for each component, remember its root, size and, additionally, a hash map that remembers the number of times ~p_x~ appears in the component.

When we need to connect two components, the newly created component is rooted in the root of the larger component. Now we must traverse the entire smaller component (e.g. using the DFS algorithm) and correct the values in the larger component's hash map.

The time complexity of this algorithm is ~\mathcal O(N \log^2 N)~.