Consider a tree consisting of n vertices. A distance between two vertices is the minimal number of edges in a path connecting them. Given a vertex vi and distance di find a vertex ui such that distance between vi and ui equals to di.
Input
The first line contains the number of vertices n (1 ≤ n ≤ 20000) and the number of queries q (1 ≤ q ≤ 50000).
Each of the following n − 1 lines describes an edge and contains the numbers of vertices connected by this edge.
Vertices are numbered from 1 to n. The next q lines describe the queries. Each query is described by a line containing two numbers vi (1 ≤ vi ≤ n) and di (0 ≤ di ≤ n).
Output
You should output q lines. The i-th line should contain a vertex number ui, the answer to the i-th query. If there are several possible answers, output any of them. If there are no required vertices, output 0 instead.
Sample
input | output |
---|
9 10
1 8
1 5
1 4
2 7
2 5
3 6
5 9
6 9
5 4
8 1
4 3
2 4
9 3
1 1
5 2
3 5
6 4
7 3
| 0
1
2
3
4
5
6
7
8
9
|
Problem Author: Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009