MAX 원소

Juku에게 정점이 $N$개인 이진 트리가 있다. 이 트리는 균형 잡혀 있지 않을 수도 있다. 정점은 $1$부터 $N$까지 번호가 매겨져 있고, 루트는 정점 $1$이다. 트리의 각 잎에는 수가 하나씩 적혀 있다. Juku는 나머지 정점마다 MIN 원소 또는 MAX 원소를 고를 수 있다. MIN 원소는 자식들의 값 중 작은 값을 자신의 값으로 쓰고, MAX 원소는 큰 값을 쓴다.

Juku는 서로 다른 수마다, 루트의 값이 그 수와 같거나 그보다 크게 되도록 하려면 MAX 원소가 최소 몇 개 필요한지 알고 싶어 한다. Juku의 질문에 답하는 프로그램을 작성하라.

첫 줄에 정점의 수 $N$이 주어진다 ($3 \le N \le 10^5$). 이어지는 $N-1$개의 줄에는 각각 두 정수 $A_i$, $B_i$ ($1 \le A_i, B_i \le N$, $A_i \ne B_i$)가 주어지며, 이는 정점 $A_i$와 $B_i$ 사이에 간선이 있다는 뜻이다.

그다음 각 줄에는 두 정수 $X_j$, $Y_j$ ($1 \le X_j \le N$, $0 \le Y_j \le 10^7$)가 주어진다. $X_j$는 잎 정점의 번호이고, $Y_j$는 그 잎에 적힌 값이다. 이러한 줄은 트리의 잎 개수만큼 있다.

다음 줄에는 질문의 개수 $Q$ ($1 \le Q \le 5 \cdot 10^5$)가 주어진다. 이어지는 $Q$개의 줄에는 각각 정수 $M_k$ ($0 \le M_k \le 10^7$)가 하나씩 주어진다.

Juku의 각 질문마다 한 줄에 답을 출력한다. 루트의 값을 $M_k$ 이상으로 만들 수 있다면, 그에 필요한 MAX 원소의 최소 개수를 출력한다. 그렇게 큰 값을 루트에 쓸 수 없다면 $-1$을 출력한다. 답은 질문이 주어진 순서대로 출력한다.