Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Reverse The Magic

By Labib666 · Limits 1s, 512 MB

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.

You can read more about it on Wikipedia. You can also read about the Tree structure on Wikipedia if you are not familiar with it.

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 &le; ui , vi < N
ui &le; 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.


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.



72% Solution Ratio

zscoderEarliest, Jan '17

sarthakmannaFastest, 0.1s

sahedsohelLightest, 524 kB

rafi_1703076Shortest, 764B


Login to submit


A few observations were required to solve this problem. The subtree under any node appears as a su...