Развитие города

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

Изначально город состоял только из исторической части. Каждый год город развивается следующим образом. Пусть в начале года в городе $m$ площадей. 

• Выбирается какая-то площадь $f$ в исторической части и какая-то площадь $t$ среди уже построенных на данный момент (в исторической или в новой части).
• Поддерево $T$ исторической части с корнем в вершине $f$ целиком копируется в новую часть, после чего корень скопированного поддерева соединяется проспектом с площадью $t$. Все построенные объекты (площади и проспекты) относятся к новой части --- историческая часть города остаётся неизменной.
• Пусть поддерево $T$ состоит из $k$ площадей. Тогда новые площади получают номера от $m+1$ до $m+k$, при этом если в поддереве $T$ номер площади $i$ меньше номера площади $j$, то номер площади $i'$, соответствующей площади $i$, меньше номера площади $j'$, соответствующей площади $j$.

Вам дана конфигурация исторической части города и данные о его развитии в течение $y$ лет. Ваша задача --- отвечать на запросы вида <<найти кратчайшее расстояние между двумя площадями>>.

Первая строка входных данных содержит три целых числа $n$, $y$ и $q$ --- число площадей в исторической части, число лет, в течение которых застраивалась новая часть, и число запросов соответственно ($1 \le n,y,q \le 10^5$).

Каждая из последующих $n-1$ строк содержит по два целых числа $a$ и $b$ --- номера двух площадей в исторической части, соединённых очередным проспектом  ($1 \le a,b \le n$; $a \ne b$). Гарантируется, что конфигурация проспектов и площадей является деревом. Главная площадь, которая является корнем дерева, имеет номер 1.

Каждая из последующих $y$ строк содержит по два целых числа $f$ и $t$ --- номер исходной площади в исторической части и номер площади, к которой присоединяется копия ($1 \le f \le n$; $t \ge 1$, $t$ не превосходит числа площадей на начало соответствующего года). 

Каждая из последующих $q$ строк содержит по два целых числа $i$ и $j$ --- номера площадей, расстояние между которыми требуется найти. Пусть $M$ --- общее число площадей по прошествии $y$ лет застройки новой части, тогда $1 \le i,j \le M$.

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