Reverse The Magic
You are probably familiar with the technique of representing a Tree as an array of integers using Euler Tour. It’s awesome. Almost as cool as a magic trick.
The following is a python code that uses this technique to represent a tree as an array of integers. You should consider this code as the only means of this conversion from tree to array for this problem. Here, A is the list that contains the array form of the tree. children [ u ] is the list of children of the node u.
def dfs ( u ) : A.append ( u ) for v in children [ u ]: dfs ( v )
Consider the following image of a tree rooted at node 8.
This code would produce the following array representation of the tree:
A = [ 8, 3, 1, 6, 4, 7, 10, 14, 13 ]
Consider the array to be 0 - indexed. Notice that the subarray [ 1 , 5 ] represents the subtree under the node 3.
We want to unveil the secret of this trick. So we want to do the opposite task. You will be helping us on our way. For this problem, you are given an integer N, the number of nodes in the tree, and M pairs of numbers ( u , v ). The subarray [ u , v ] of the array representation, A, should represent a subtree of the tree to be constructed.
For now, all you have to do is tell us if such a tree can be constructed so that it produces an array representation A conforming to these given conditions.
The first line of the input contains an integer T, the number of test cases.
Each test case starts with two space-separated integers, N and M.
The following M lines contain a pair of space-separated integers each. The pairs are not necessarily distinct. Let ( ui , vi ) represent the pair of elements on the i - th line. You have to verify if a tree can be constructed such that, in its Euler Tour representation A, each of the subarrays [ ui , vi ] represents a subtree in the original tree.
1 ≤ T ≤ 10
1 ≤ N ≤ 105
1 ≤ M ≤ N
0 ≤ ui , vi < N
ui ≤ vi
For each test case, on a separate line, print “Yes” (without the quotes) if such a tree can be constructed. Print “No” (without the quotes) otherwise.
2 9 3 0 8 1 5 6 8 5 2 1 3 3 4
For the first test case, the tree in the image above satisfies the given conditions.
In the second case, no such tree can be constructed.
Labib666Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms. →