BFS 스페셜 저지

정답이 여러 가지인 문제를 채점할 때는 스페셜 저지를 쓴다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드로 정답 여부를 결정하는 방식이다. 이 문제에서는 스페셜 저지 코드를 하나 만들어 보려고 한다.

정점이 N개이고 정점에 1부터 N까지 번호가 매겨진 양방향 그래프에서 BFS 알고리즘은 다음과 같이 동작한다.

1. 큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.

2. 큐가 비어 있지 않은 동안 다음을 반복한다.

   1. 큐에 들어 있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
   2. x와 연결되어 있으면서 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.

2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서 BFS의 결과는 여러 가지가 나올 수 있다.

트리가 주어졌을 때, 주어진 방문 순서가 올바른 BFS 방문 순서인지 판별하자.

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 BFS 방문 순서가 주어진다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

입력으로 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.