New update is available. Click here to update.

Last Updated: 18 Mar, 2021

Difficulty: Hard

```
1. Xi < Yi.
2. There is no duplicate in the ‘PAIRS’ array.
```

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

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

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

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

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

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

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

SIMILAR PROBLEMS

Ninja And The Class Room

Posted: 19 Sep, 2022

Difficulty: Easy

Equal Arrays

Posted: 29 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximize

Posted: 9 Dec, 2022

Difficulty: Easy

Popular Interview Problems: