You are given an array
pairs[i] = [xi, yi], and:
xi < yi
ways be the number of rooted trees that satisfy the following conditions:
[xi, yi]exists in
pairsif and only if
xiis an ancestor of
yiis an ancestor of
Two ways are considered to be different if there is at least one node that has different parents in both ways.
ways == 0
ways == 1
ways > 1
A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.
An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.
Input: pairs = [[1,2],[2,3]] Output: 1 Explanation: There is exactly one valid rooted tree, which is shown in the above figure.
Input: pairs = [[1,2],[2,3],[1,3]] Output: 2 Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.
Input: pairs = [[1,2],[2,3],[2,4],[1,5]] Output: 0 Explanation: There are no valid rooted trees.
1 <= pairs.length <= 105
1 <= xi < yi <= 500