I. Tree Chase
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is chasing Bob through a network of $$$n$$$ rooms. The network is organized as a rooted tree of rooms, numbered from $$$1$$$ to $$$n$$$ and rooted at room $$$1$$$.

At the start of the game, Alice only has control of room $$$A$$$, and Bob is located in room $$$B$$$. It is guaranteed that room $$$A$$$ is the parent of room $$$B$$$.

Each day consists of two sequential phases, in the following order:

1. Bob must choose to either:

  • Teleport to an ancestor of his current room that is $$$i$$$ edges away, where $$$0 \leq i \leq K$$$. The destination can't be controlled by Alice, but Bob may pass through intermediate rooms along the path that are controlled by Alice
  • Move to any child of his current room that is not controlled by Alice

2. Alice takes control of exactly one room adjacent to her currently controlled territory. If the newly controlled room is the one Bob is currently in, Bob is captured and the game ends immediately.

Bob wants to maximize the number of days he evades capture, while Alice wants to capture him as quickly as possible. Both players play optimally and have perfect information about the state of the network at all times. Your task is to find the number of days Bob would survive, including the day he is captured.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 30000)$$$, representing the number of test cases.

The first line of each test case contains three integers $$$n, K, B$$$ $$$(2 \leq n \leq 2 \cdot 10^5, 1 \leq K \leq n, 2 \leq B \leq n)$$$.

The second line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_n$$$, where $$$p_i$$$ is the parent of room $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer, the number of days Bob survives.

Scoring
SubtaskConstraintPoints
$$$1$$$$$$p_i = i - 1$$$$$$40$$$
$$$2$$$$$$n \leq 300, \sum n \leq 5000$$$$$$40$$$
$$$3$$$$$$n \leq 3000, \sum n \leq 50000$$$$$$40$$$
$$$4$$$No additional constraints$$$80$$$
Example
Input
4
2 1 2
1
6 1 4
1 2 3 4 5
8 2 5
1 2 3 4 2 6 7
8 3 5
1 2 3 4 2 6 7
Output
1
3
1
5
Note

In the fourth example, Bob can teleport to room $$$2$$$, then move down $$$2 \rightarrow 6 \rightarrow 7 \rightarrow 8$$$. It can be proven that Alice will capture Bob in $$$5$$$ days if she moves optimally.