Message Propagation in a Tree Social Network

You are given a tree social network with \(n\) persons numbered from \(1\) to \(n\). The network is represented as a tree where each pair of persons that share a direct social relationship is connected by an edge.

The message spreading mechanism works as follows: if a person receives a message on day \(d\), then on day \(d+1\) he or she will forward the message to all persons who are directly connected. Note that once a person has received the message, receiving it again in later days is not counted as a new reception.

You will be given \(m\) queries. In each query, assume that on day \(0\) a given person \(x\) receives the message. Your task is to determine the number of persons who receive the message for the first time on day \(k\) (i.e. people who have not received the message in any of the previous days).

In other words, if we define the distance from \(x\) in the tree as the minimum number of edges that need to be traversed, then the answer for a query is the number of nodes that are exactly at distance \(k\) from \(x\).

inputFormat

The first line contains two integers \(n\) and \(m\): the number of persons in the network and the number of queries, respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating that there is an undirected edge between person \(u\) and person \(v\).

The following \(m\) lines each contain two integers \(x\) and \(k\) representing a query: on day \(0\), person \(x\) receives the message, and you are to determine the number of persons who receive the message for the first time on day \(k\).

outputFormat

For each query, output a single integer on a new line representing the number of persons who receive the message for the first time on day \(k\).

sample

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

2
1
1