Check BFS Traversal Validity

Given a tree (a graph with no cycles) with n vertices and a BFS traversal indicating the sequence of vertices that were visited by the algorithm, you are asked to check if that sequence of visits is possible.
The algorithm always starts at vertex 1 and traverses the neighbors in no particular order. Your program should print Yes in case this traversal is possible for the given tree, and No otherwise.
As a reminder, a tree always has n-1 edges.


The first line of the input contains a single integer n (1 ≀ n ≀ 100 000).
The next n-1 lines contain pairs of integers (1 ≀ ≀ n) representing the edges.
The following line contains n space-separated integers (1 ≀ ≀ n) representing the sequence of visits by the BFS algorithm.


The program should print Yes if a given scenario is valid, and No otherwise.


4 1 2 1 3 2 4 1 2 3 4
4 1 2 1 3 2 4 1 2 4 3


Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in