ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## K. 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
To submit the solution for this problem go to the Problem set: 1752. Tree 2