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

문제

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

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

• Выбирается какая-то площадь $ff$ в исторической части и какая-то площадь $tt$ среди уже построенных на данный момент (в исторической или в новой части).
• Поддерево $TT$ исторической части с корнем в вершине $ff$ целиком копируется в новую часть, после чего корень скопированного поддерева соединяется проспектом с площадью $tt$. Все построенные объекты (площади и проспекты) относятся к новой части --- историческая часть города остаётся неизменной.
• Пусть поддерево $TT$ состоит из $kk$ площадей. Тогда новые площади получают номера от $m+1m+1$ до $m+km+k$, при этом если в поддереве $TT$ номер площади $ii$ меньше номера площади $jj$, то номер площади $i^{\mathrm{\prime }}i\text{'}$, соответствующей площади $ii$, меньше номера площади $j^{\mathrm{\prime }}j\text{'}$, соответствующей площади $jj$.

[이미지 1]

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

입력

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

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

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

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

출력

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