問題文

N 頂点の木があります。i 本目の辺は、頂点 A_i と B_i を結んでいます。

次のクエリ Q 個に答えてください。

• 頂点 v_i からちょうど k_i 本の辺を引き返すことなしに通って辿り着くことのできる頂点の個数を求めよ。

制約

• 1 \leq N,Q \leq 10^5
• 1 \leq A_i,B_i \leq N(1\leq i\leq N-1)
• 1 \leq v_i \leq N(1\leq i\leq Q)
• 0 \leq k_i \leq N - 1(1\leq i\leq Q)
• 入力で与えられるグラフは木である
• 入力はすべて整数である

入力例 1

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

出力例 1

1
2
1
0
1

• 1 つめのクエリに対し、頂点 1 からちょうど 0 本の辺を通って辿り着くことのできる頂点は頂点 1 のみです。よって、1 を出力します。
• 2 つめのクエリに対し、頂点 2 からちょうど 1 本の辺を通って辿り着くことのできる頂点は頂点 2,3 です。よって、2 を出力します。
• 3 つめのクエリに対し、頂点 3 からちょうど 2 本の辺を通って辿り着くことのできる頂点は頂点 4 のみです。よって、1 を出力します。
• 4 つめのクエリに対し、頂点 4 からちょうど 4 本の辺を通って辿り着くことのできる頂点はありません。よって、0 を出力します。
• 5 つめのクエリに対し、頂点 5 からちょうど 1 本の辺を通って辿り着くことのできる頂点は頂点 3 のみです。よって、1 を出力します。

入力例 2

7 35
1 2
2 3
1 4
1 5
5 6
5 7
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
6 0
6 1
6 2
6 3
6 4
7 0
7 1
7 2
7 3
7 4

出力例 2

1
3
3
0
0
1
2
2
2
0
1
1
1
2
2
1
1
2
3
0
1
3
2
1
0
1
1
2
2
1
1
1
2
2
1