28565번 - Патруль экзорцистов 다국어

문제

Из-за того, что на Хэллоуин все наряжаются в жуткие костюмы, экзорцистам становится особенно сложно различать людей и настоящих демонов. Но работа есть работа, а значит и в Хэллоуинскую ночь им приходится патрулировать город в поисках нечисти.

Город состоит из $n$ площадей, между которыми проходят $n - 1$ улиц. Известно, что по любой улице можно перемещаться в любом направлении, а так же что от каждой площади можно добраться по улицам до любой другой. Периодически патрулирующие город экзорцисты обнаруживают потустороннее существо на какой-то площади, после чего высылается отряд для поимки существа.

Если существо со скоростью $d$ было обнаружено на площади $v,ドル оно может скрыться от экзорцистов, если есть путь от площади $v$ до площади на расстоянии строго больше $d$ от нее. Чтобы не упустить демона, перед тем, как высылать отряд, экзорцисты перекрывают некоторые улицы. Ваша задача --- помочь экзорцистам оптимизировать этот процесс. Поскольку в городе праздник, хочется перекрывать как можно меньше улиц!

Для каждого из $m$ событий вида <<обнаружен демон со скоростью $d_i$ на площади $v_i$>> определите, какое минимальное количество улиц надо перекрыть, чтобы с площади $v_i$ были недостижимы площади на расстоянии, большем чем $d_i,ドル от нее.

입력

В первой строке через пробел даны два числа $n$ и $m$ --- количество площадей в городе и количество событий о нахождении нечисти (1ドル \leq n, m \leq {10}^5$).

В следующих $n - 1$ строках по одной на строке находятся пары чисел $a_i,ドル $b_i$ --- номера площадей, соединенных $i$-й улицей (1ドル \leq a_i, b_i \leq n$; $a_i \neq b_i$).

В следующих $m$ строках перечислены пары чисел $v_i$ и $d_i$ --- запросы на поимку нечисти (1ドル \leq v_i \leq n$; 0ドル \leq d \leq n$).

출력

Для каждого запроса на поимку демона выведите в отдельной строке ответ на него --- минимальное количество улиц, которое надо перекрыть, чтобы он не смог сбежать.

제한

힌트