29352번 - Канализация 다국어

문제

Как известно, черепашки-ниндзя вместе со своим учителем Сплинтером всю свою жизнь проводят в канализации. Ведь только там можно так быстро передвигаться по городу, скользя на панцире! Из канализации в город можно выбраться только с помощью $n$ канализационных люков, расположенных в разных частях города. Некоторые люки соединены друг с другом трубами, по которым черепашки могут передвигаться в обе стороны. Между каждой парой люков существует ровно один путь по трубам. Это, в частности, значит, что в канализации ровно $n - 1$ труба. Люки пронумерованы начиная с 1ドル$.

Когда черепашки-ниндзя были маленькими, они постоянно забывали маршруты от одного люка до другого, и спрашивали учителя Сплинтера, куда же им скользить, чтобы попасть в какой-то люк. Сплинтер сообщал черепашкам номер первого люка на пути из люка номера $l$ к люку номер $r$.

Вскоре учителю Сплинтеру надоело, что черепашки постоянно отвлекают его от медитации, и они вместе с Донателло написали программу, которая по двум номерам люков $l$ и $r$ сообщает номер первого люка на пути из $l$ в $r$. А вы сможете написать такую программу?

입력

В первой строке входного файла заданы два целых числа $n$ и $m$ --- количество люков в канализации и количество запросов соответственно (1ドル \le n, m \le 10^5$).

В следующих $n - 1$ строке заданы описания труб --- два числа $a$ и $b,ドル которые задают номера люков, которые соединяет эта труба (1ドル \le a, b \le n$). По трубе можно скользить в обоих направлениях. Гарантируется, что в канализации можно добраться от каждого люка до каждого.

В следующих $m$ строках заданы запросы, по одному запросу в строке --- два числа $l$ и $r,ドル которые задают стартовый и конечный люк на пути соответственно (1ドル \le l, r \le n$). Гарантируется, что $l$ и $r$ --- различны.

출력

В выходной файл выведите ответы на запросы по одному в строке, в том порядке, в котором они следуют во входном файле. Ответом на запрос является номер первого люка на пути с $l$ по $r$.

제한

힌트