DFS Special Judge

When a problem has multiple correct answers, a special judge is used. A special judge decides whether an answer is correct by running code that verifies the user's output. Today we are going to write one such special judge.

For an undirected graph with N vertices numbered 1 to N, the DFS algorithm takes the following form.

void dfs(int x) {
    if (check[x] == true) {
        return;
    }
    check[x] = true;
    // visit x
    for (int y : vertices adjacent to x) {
        if (check[y] == false) {
            dfs(y);
        }
    }
}

In this problem the starting vertex is 1, so the first call is dfs(1). The DFS visit order is the sequence of vertex numbers reached at the point marked // visit x inside dfs.

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

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

Print 1 if the given DFS visit order is valid, and 0 otherwise.