Gug the Amoeba has a long family heritage. There are a total of *N* amoeba in his family, with the eldest of them all being Amoeba 0. For all other amoebas, they have a single parent. Namely, amoeba *i* has parent P_{i}. It is guaranteed that there will be no loops in the family tree, meaning that no direct or indirect parent of an amoeba will be itself.

We call a pair of distinct amoebas *k*-cousins if they share a common *k*-th parent. Gug wants to know, for some amoebas in his family, how many *k*-cousins they have.

This is a function call problem. You are to implement 2 functions:

void init(int N, int P[])

This function will be called before any of the other functions in your code. `N`

is the number of amoebas in Gug's family tree and `P`

is the parent array of his family tree. Since Amoeba 0 has no parent, P_{0} = -1.

int count_cousins(int X, int K)

This function should return the number of `K`

-cousins that Amoeba `X`

has. It is guaranteed that Amoeba `X`

has at least `K`

parents.

Subtask 1 (27%): 1 ≤ N ≤ 1000, Number of calls to `count_cousins`

≤ 3000.

Subtask 2 (20%): 1 ≤ N ≤ 200000, K ≤ 5, Number of calls to `count_cousins`

≤ 300000.

Subtask 3 (22%): 1 ≤ N ≤ 200000, K is a constant throughout all calls to `count_cousins`

, Number of calls to `count_cousins`

≤ 300000.

Subtask 4 (31%): 1 ≤ N ≤ 200000, Number of calls to `count_cousins`

≤ 300000.

Subtask 5 (0%): Sample Testcases.

`init(7, [-1, 0, 1, 1, 0, 4, 4])`

will be called.`count_cousins(2, 1)`

is called. It should return `1`

.`count_cousins(6, 1)`

is called. It should return `1`

.`count_cousins(3, 2)`

is called. It should return `3`

.
Subtask | Score |
---|---|

1 | 27 |

2 | 20 |

3 | 22 |

4 | 31 |

5 | 0 |