You are given a $2$D integer array pairs, where pairs[i] = [x_i, y_i] indicates that there is an ancestor or descendant relationship between nodes x_i and y_i in a rooted tree. That is, either x_i is an ancestor of y_i, or y_i is an ancestor of x_i.

A rooted tree is valid if:

• It contains all nodes that appear in pairs.

• For every pair [x_i, y_i] in pairs, either x_i is an ancestor of y_i or y_i is an ancestor of x_i.

• For any two nodes not in pairs, neither is an ancestor of the other.

Return:

• $0$ if no valid rooted tree exists.

• $1$ if there is exactly $1$ valid rooted tree.

• $2$ if there are $2$ or more valid rooted trees.

Note: A node u is an ancestor of v if u lies on the path from the root to v and u \neq v.

Constraints:

• $1 \leq$ pairs.length $\leq 10^5$

• $1 \leq$ x_i $<$ y_i $\leq 500$

• The elements in pairs are unique.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.