409206: GYM103456 I Exiting the Maze

The organizers of Squid Game have added a new task. In this task, the contestants find themselves lost in a strange maze. Please help them answer some questions and better understand their predicament.

In this maze, there are $$$N$$$ different rooms numbered $$$1...N$$$, linked by doors in such a way that all rooms are connected and only $$$N - 1$$$ doors exist (connecting exactly two rooms each). The Squid Game organizers are in the main room, room $$$1$$$, and are kind enough to volunteer to bring back contestants if they get close enough to the main room.

There are $$$Q$$$ contestants. Each contestant $$$i$$$ finds themselves in a room $$$r_i$$$ and are told they will be rescued immediately if they are within $$$d_i$$$ of room $$$1$$$. For each contestant, please determine the room in which they will be rescued.

The first line contains two integers: $$$1 \leq N, Q \leq 100,000$$$

The next $$$N-1$$$ lines describe the doors with the $$$i$$$th line containing two space-separated integers $$$u_i$$$ and $$$v_{i}$$$, linking the two specified rooms ($$$1 \leq u_i, v_i \leq N$$$). Each pair of rooms that are connected will be listed exactly.

The last $$$Q$$$ lines describe each contestant, providing the values $$$r_i$$$ ($$$1 \leq r_i \leq N$$$) and $$$d_i$$$ ($$$0 \leq d_i \leq N$$$) representing the starting room and the distance that the participant must be within from room $$$1$$$ to be rescued.

Each line describes the room in which the corresponding contestant will be rescued.

7 4
1 2
2 7
1 3
4 3
4 5
4 6
5 1
6 2
2 0
7 2

3
4
1
7

A contestant may begin within $$$d_i$$$ of room $$$1$$$.