7146: ABC267 —— F - Exactly K Steps
[Creator : ]
Description
You are given a tree with N vertices. The vertices are numbered $1, \dots, N$, and the i-th ($1 \leq i \leq N - 1$) edge connects Vertices $A_i$ and $B_i$.
We define the distance between Vertices $u$ and $v$ on this tree by the number of edges in the shortest path from Vertex u to Vertex v.
You are given $Q$ queries. In the i-th ($1 \leq i \leq Q$) query, given integers $U_i$ and $K_i$, print the index of any vertex whose distance from Vertex $U_i$ is exactly $K_i$. If there is no such vertex, print $-1$.
We define the distance between Vertices $u$ and $v$ on this tree by the number of edges in the shortest path from Vertex u to Vertex v.
You are given $Q$ queries. In the i-th ($1 \leq i \leq Q$) query, given integers $U_i$ and $K_i$, print the index of any vertex whose distance from Vertex $U_i$ is exactly $K_i$. If there is no such vertex, print $-1$.
Input
Input is given from Standard Input in the following format:
$N$
$A_1\ B_1$
$\vdots$
$A_{N-1}\ B_{N-1}$
$Q$
$U_1\ K_1$
$\vdots$
$U_Q\ K_Q$
$N$
$A_1\ B_1$
$\vdots$
$A_{N-1}\ B_{N-1}$
$Q$
$U_1\ K_1$
$\vdots$
$U_Q\ K_Q$
Output
Print $Q$ lines. The i-th ($1 \leq i \leq Q$) line should contain the index of any vertex whose distance from Vertex $U_i$ is exactly $K_i$ if such a vertex exists; if not, it should contain -1.
If there are multiple such vertices, you may print any of them.
If there are multiple such vertices, you may print any of them.
Constraints
$2≤N≤2×10^5$
$1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)$
The given graph is a tree.
$1 \leq Q \leq 2 \times 10^5$
$1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)$
All values in input are integers.
$1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)$
The given graph is a tree.
$1 \leq Q \leq 2 \times 10^5$
$1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)$
All values in input are integers.
Sample 1 Input
5
1 2
2 3
3 4
3 5
3
2 2
5 3
3 3
Sample 1 Output
4
1
-1
- Two vertices, Vertices 4 and 5, have a distance exactly 2 from Vertex 2.
- Only Vertex 1 has a distance exactly 3 from Vertex 5.
- No vertex has a distance exactly 3 from Vertex 3.
Sample 2 Input
10
1 2
2 3
3 5
2 8
3 4
4 6
4 9
5 7
9 10
5
1 1
2 2
3 3
4 4
5 5
Sample 2 Output
2
4
10
-1
-1