Number Of Ways To Reconstruct A Tree

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.