Problem Description

There are $n$ players playing a certain card game, numbered from $1$ to $n$. The players form a tree structure. Player $i$ initially has $a_i$ cards and $b_i$ energy points. You are player $d$.

At the beginning of the game, everyone agrees on an integer $u$. Then player $u$ chooses a permutation $p_1,\ldots,p_n$, such that $p$ is a DFS order of the original tree when rooted at $u$.

Initially, let $k=0$. Then for each $i=1,2,\ldots,n$ in order, player $p_i$ must choose exactly one of the following actions:

1. Discard some cards from their hand. The number of discarded cards must be at most $a_{p_i}$, and must be at least the number discarded by the previous player who chose to discard, plus $1$.
   Formally, choose an integer $x$ such that $k < x \le a_{p_i}$, and set $k \gets x$.
   In particular, if $\boldsymbol{k \ge a_{p_i}}$, then this action cannot be chosen.

2. Lose $2$ energy points.
   Formally, set $b_{p_i} \gets b_{p_i} - 2$.

Once a player's remaining energy becomes $\le 0$, they are eliminated.

You win if and only if after the entire process ends, you are not eliminated, regardless of whether other players are eliminated.

You want to know how many integers $u$ with $1 \le u \le n$ satisfy the following:

There exists some strategy of the other players (excluding you), such that no matter what you do, you will inevitably lose.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, denoting the number of test cases.

For each test case:

The first line contains two positive integers $n,d$, representing the number of nodes in the tree and your player index.

The next $n$ lines each contain two integers $a_i,b_i$.

The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between nodes $u$ and $v$ in the tree.

Output Format

For each test case, output one line containing one integer: the required answer.

1
5 1
1 2
2 2
1 1
3 2
4 2
1 2
1 3
3 4
3 5

4

1
5 3
2 3
3 3
1 6
6 2
8 6
1 2
1 3
3 4
4 5

0

Hint

Explanation of Sample 1

When $u \in \{2,3,4,5\}$, there exists an optimal strategy for the opponents that guarantees your failure.

For example, when $u=3$, one possible DFS order rooted at $3$ is $3,4,1,2,5$. Following this order:

• Player $3$ chooses to lose $2$ energy points.
• Player $4$ chooses to discard $a_4=2$ cards.

Then you (player $1$) must discard at least $2+1=3$ cards, but $a_1=1$, so you cannot choose the discard action. You are forced to lose $2$ energy points and are eliminated immediately. Therefore, you lose.

Explanation of Sample 2

Since $b_3>2$, no matter what strategy the opponents use, you can always choose to lose $2$ energy points without being eliminated. Therefore, you are guaranteed to win.

Constraints

This problem uses bundled subtasks.

Special property $\text{A}$: it is guaranteed that $T \le 5$.

Special property $\text{B}$: the tree is generated as follows: after fixing $n$, for each $2 \le i \le n$, an integer $x$ is chosen uniformly at random from $[1,i)$, and an edge is added between $x$ and $i$.

Special property $\text{C}$: it is guaranteed that $a_i \le 10$.

For all test cases, it is guaranteed that $T \le 100$, $2 \le n \le 10^5$, $\sum n \le 10^6$, $1 \le a_i,b_i \le 10^9$, $1 \le d \le n$.