트리 호핑

트리와 그 정점들의 순열이 주어진다. 어떤 트리와 어떤 출발/도착 노드 쌍에 대해서도, 첫 번째 노드가 출발 노드이고 마지막 노드가 도착 노드이며 순열에서 인접한 노드 사이의 거리가 3 이하인 순열이 존재한다는 것이 증명될 수 있다.

여러분의 임무는 이 성질을 검증하는 프로그램을 작성하는 것이다. 이러한 순열과 트리가 주어졌을 때, 순열에서 인접한 노드 사이의 거리가 3 이하인지 검증하라.

입력의 첫 번째 줄에는 정수 $t$ ($1 \le t \le 50{,}000$)가 주어지며, 이는 테스트 케이스의 수이다.

각 테스트 케이스에서 입력의 첫 번째 줄에는 정수 $n$ ($2 \le n \le 100{,}000$)이 주어지며, 이는 트리의 노드 수이다. 노드는 $1$부터 $n$까지 번호가 매겨져 있다.

다음 $n-1$개의 줄에는 각각 두 정수 $a$와 $b$ ($1 \le a < b \le n$)가 주어지며, 이는 노드 $a$와 노드 $b$를 잇는 트리의 간선을 나타낸다.

그다음 $n$개의 줄에는 각각 정수 $p$ ($1 \le p \le n$, 모든 값은 서로 다름)가 주어진다. 이는 노드들의 순열이다.

모든 테스트 케이스에 걸친 $n$의 합은 $100{,}000$을 넘지 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 주어진 순열이 순열에서 인접한 모든 노드 쌍의 트리에서의 거리가 3 이하라는 조건을 만족하면 $1$을 출력한다. 주어진 순열이 이 조건을 만족하지 않으면 $0$을 출력한다.