B. Fake Plastic Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The root of the tree is the vertex $$$1$$$ and the parent of the vertex $$$v$$$ is $$$p_v$$$.

There is a number written on each vertex, initially all numbers are equal to $$$0$$$. Let's denote the number written on the vertex $$$v$$$ as $$$a_v$$$.

For each $$$v$$$, we want $$$a_v$$$ to be between $$$l_v$$$ and $$$r_v$$$ $$$(l_v \leq a_v \leq r_v)$$$.

In a single operation we do the following:

  • Choose some vertex $$$v$$$. Let $$$b_1, b_2, \ldots, b_k$$$ be vertices on the path from the vertex $$$1$$$ to vertex $$$v$$$ (meaning $$$b_1 = 1$$$, $$$b_k = v$$$ and $$$b_i = p_{b_{i + 1}}$$$).
  • Choose a non-decreasing array $$$c$$$ of length $$$k$$$ of nonnegative integers: $$$0 \leq c_1 \leq c_2 \leq \ldots \leq c_k$$$.
  • For each $$$i$$$ $$$(1 \leq i \leq k)$$$, increase $$$a_{b_i}$$$ by $$$c_i$$$.

What's the minimum number of operations needed to achieve our goal?

Input

The first line contains an integer $$$t$$$ $$$(1\le t\le 1000)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(2\le n\le 2 \cdot 10^5)$$$  — the number of the vertices in the tree.

The second line of each test case contains $$$n - 1$$$ integers, $$$p_2, p_3, \ldots, p_n$$$ $$$(1 \leq p_i < i)$$$, where $$$p_i$$$ denotes the parent of the vertex $$$i$$$.

The $$$i$$$-th of the following $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \le r_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case output the minimum number of operations needed.

Example
Input
4
2
1
1 5
2 9
3
1 1
4 5
2 4
6 10
4
1 2 1
6 9
5 6
4 5
2 4
5
1 2 3 4
5 5
4 4
3 3
2 2
1 1
Output
1
2
2
5
Note

In the first test case, we can achieve the goal with a single operation: choose $$$v = 2$$$ and $$$c = [1, 2]$$$, resulting in $$$a_1 = 1, a_2 = 2$$$.

In the second test case, we can achieve the goal with two operations: first, choose $$$v = 2$$$ and $$$c = [3, 3]$$$, resulting in $$$a_1 = 3, a_2 = 3, a_3 = 0$$$. Then, choose $$$v = 3, c = [2, 7]$$$, resulting in $$$a_1 = 5, a_2 = 3, a_3 = 7$$$.