| English | 简体中文 |

# 1719. Number Of Ways To Reconstruct A Tree

## Description

You are given an array `pairs`

, where `pairs[i] = [x`

, and:_{i}, y_{i}]

- There are no duplicates.
`x`

_{i}< y_{i}

Let `ways`

be the number of rooted trees that satisfy the following conditions:

- The tree consists of nodes whose values appeared in
`pairs`

. - A pair
`[x`

exists in_{i}, y_{i}]`pairs`

**if and only if**`x`

is an ancestor of_{i}`y`

or_{i}`y`

is an ancestor of_{i}`x`

._{i} **Note:**the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

`0`

if`ways == 0`

`1`

if`ways == 1`

`2`

if`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.

**Example 1:**

Input:pairs = [[1,2],[2,3]]Output:1Explanation:There is exactly one valid rooted tree, which is shown in the above figure.

**Example 2:**

Input:pairs = [[1,2],[2,3],[1,3]]Output:2Explanation:There are multiple valid rooted trees. Three of them are shown in the above figures.

**Example 3:**

Input:pairs = [[1,2],[2,3],[2,4],[1,5]]Output:0Explanation:There are no valid rooted trees.

**Constraints:**

`1 <= pairs.length <= 10`

^{5}`1 <= x`

_{i }< y_{i}<= 500- The elements in
`pairs`

are unique.