# Number Of Ways To Reconstruct A Tree

Last Updated: 18 Mar, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### You are given an array ‘PAIRS’ consisting of ‘N’ pairs, where PAIRS[i] = [Xi, Yi] such that:

``````1. Xi < Yi.

2. There is no duplicate in the ‘PAIRS’ array.
``````

#### You have to determine the number of ways to reconstruct a rooted tree that satisfies the following conditions:

``````1. The nodes of the tree must be present in the ‘PAIRS’ array.

2. A pair [Xi, Yi] exists in pairs if and only if Xi is an ancestor of Yi or Yi is an ancestor of Xi.
``````

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

##### You should return:
``````1. 0, if there is no way to reconstruct a tree.

2. 1, if there is exactly 1 way.

3. 2, if there is more than 1 way.
``````

#### Note:

``````1. The tree does not necessarily have to be a binary tree.

2. A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

3. An ancestor of a node is any node on the path from the root to that node. The root has no ancestors.
``````
##### Input Format:
``````The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’, as described in the problem statement.

Then next ‘N’ lines contain two space-separated integers denoting the pair [Xi, Yi], as described in the problem statement.
``````
##### Output Format:
``````For each test case, print a single line containing either ‘0’,’1’, or ‘2’ depending on the number of ways to reconstruct the rooted tree.

The output of every test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10 ^ 5
1 <= Xi < Yi <= 500

Where ‘T’ denotes the number of test cases and ‘N’ denotes the size of ‘PAIRS’.

Time Limit: 1 sec.
``````