Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вся поверхность столичной планеты Трантор покрыта огромным городом. Самый быстрый способ
перемещения по нему -- скоростной монорельс. Все станции монорельса связаны двусторонними линиями
в единую сеть и от любой станции можно добраться до любой другой (возможно, с пересадками).
К сожалению, инфраструктура Трантора находится в упадке, и работоспособность сохраняет
только минимально необходимое количество линий. Из-за этого между каждой парой станций остается
только 1 возможный маршрут. Что еще хуже, поезда регулярно ломаются: в этом случае пассажиры не
доезжают до конечной станции, а застревают на одной из промежуточных остановок и вынуждены ждать другого поезда.
Прибывший на Трантор математик Гэри Селдон не привык к подобным проблемам, и в первый же день заблудился
по дороге из космопорта (станция 1).
Селдон описал свои поездки в дневнике следующим образом:
* он садился в поезд и запоминал номер конечной станции, до которой поезд следовал по расписанию;
* во время поездки он считал количество станций, которые поезд успешно миновал по дороге;
* если поезд ломался, не доехав до конечной станции, Селдон покидал его на текущей станции, а затем садился в первый же подошедший на эту станцию поезд (возможно, следующий другим маршрутом или в другую сторону);
* в новом поезде все повторялось снова.
К сожалению, во время одной из пересадок Селдон забыл на станции свой портфель с бесценными записями. Помогите
ему определить, на каких станциях он побывал, чтобы попытаться его найти.
В первой строке ввода содержатся два целых числа: количество станций `N` (`2<=N<=10^5`) и
количество записей Селдона о его поездках `M` (`1<=M<=10^5`).
Затем следует `N-1` строка -- описание сети монорельса. Каждая строка содержит по два целых числа:
номера станций, связанных между собой линией (станции нумеруются от `1` до `N`).
Затем следует `M` строк, описывающих поездки Селдона.
Каждая строка содержит по два целых числа: номер конечной станции, в направлении которой следовал поезд (от 1 до `N`), и
количество станций `K`, которые Селдон проехал на поезде до поломки (считая станцию отправления, но не считая станцию, на которой поезд остановился).
Гарантируется, что `K` не меньше 1 и не больше, чем количество станций до конечной. Первая поездка начинается со станции с номером 1.
Выведите `M` целых чисел -- номера станций, на которых Селдон оказывался по окончании каждой из своих поездок.
```sample Пример ввода
7 4
1 2
2 3
3 4
4 5
3 6
6 7
7 3
5 2
2 1
7 2
```
```sample Пример вывода
6 4 3 7
```
*Пояснение к примеру.*
* Первая поездка (7, 3): поезд от станции 1 до станции 7 следует по маршруту 1-2-3-6-7; проехав на нем 3 станции, Селдон остановился на станции 6.
* Вторая поездка (5, 2): поезд от станции 6 до станции 5 следует по маршруту 6-3-4-5; проехав на нем 2 станции, Селдон остановился на станции 4.
* Третья поездка (2, 1): поезд от станции 4 до станции 2 следует по маршруту 4-3-2; проехав на нем 1 станцию, Селдон остановился на станции 3.
* Четвертая поездка (7, 2): поезд от станции 3 до станции 7 следует по маршруту 3-6-7; проехав на нем 2 станции, Селдон добрался до конечной станции 7.
Начало
Рабочее место участника
Наименьший общий предок (LCA)