ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1752. Tree 2

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ vin) and di (0 ≤ din).

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

inputoutput
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