BFS Special Judge

Interview

Time limit2sMemory limit512 MB

Summary

Given a tree and a permutation of its vertices, decide whether the permutation can be produced by a BFS traversal starting from vertex 1.

Level: Medium5 of 10
Topics: BFS, Tree, Graph, Implementation
Solved: No attempts yet

Problem

When a problem has multiple correct answers, it is graded with a special judge. A special judge is a piece of code that checks the answer a user submitted and decides whether it is correct. Today we are going to write a special judge.

For an undirected graph with N vertices numbered 1 through N, the BFS algorithm works as follows.

Put the start vertex into the queue. In this problem the start vertex is 1. Mark 1 as visited.
While the queue is not empty, repeat the following.
1. Take the first vertex out of the queue. Call this vertex x.
2. For every vertex y that is adjacent to x and not yet visited, put y into the queue. Mark every y as visited.

In step 2-2 the order in which the unvisited vertices are visited does not matter. Therefore a BFS can produce several different results.

Given a tree, determine whether the given visit order is a valid BFS visit order.

Input

The first line gives the number of vertices N (2 ≤ N ≤ 100,000). Each of the next N-1 lines gives an edge of the tree. The last line gives a BFS visit order. The BFS visit order always consists of N integers, and each integer from 1 to N appears exactly once.

Output

Print 1 if the BFS visit order given in the input is valid, and 0 otherwise.

Examples2

Example 1
Input
```
4
1 2
1 3
2 4
1 2 3 4
```
Expected output
```
1
```
Example 2
Input
```
4
1 2
1 3
2 4
1 2 4 3
```
Expected output
```
0
```