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.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000).The next
n-1 lines contain pairs of integers The following line contains
n space-separated integers Output
The program should print
Yes if a given scenario is valid, and No otherwise.Examples
Input | Output |
4
1 2
1 3
2 4
1 2 3 4 | Yes |
4
1 2
1 3
2 4
1 2 4 3 | No |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB