Расстояние на триангуляции
Расстояние на триангуляции
Имеется правильный многоугольник. Вершины многоугольника последовательно пронумерованы числами от 1 до n. Имеется также триангуляция этого многоугольника, заданная списком из n − 3 диагоналей.
Заданы q запросов. Каждый запрос задается номерами двух вершин. Для каждого запроса найдите кратчайшее расстояние между этими двумя вершинами, двигаясь по сторонам или заданным диагоналям многоугольника, расстояние равно общему количеству пройденных сторон и диагоналей.
Входные данные
Первая строка содержит количество вершин в многоугольнике n (4 ≤ n ≤ 50 000).
Каждая из следующих n − 3 строк содержит два числа ai
, bi
- концы i-ой диагонали (1 ≤ ai
, bi
≤ n, ai
≠ bi
).
Следующая строка содержит количество запросов q (1 ≤ q ≤ 100 000).
Каждая из следующих q строк содержит два целых числа xi
, yi
(1 ≤ xi
, yi
≤ n) - вершины i-го запроса. Гарантируется, что никакая диагональ не совпадает со стороной многоугольника и никакие две диагонали не совпадают и не пересекаются.
Выходные данные
Для каждого запроса выведите в отдельной строке кратчайшее расстояние.
6 1 5 2 4 5 2 5 1 3 2 5 3 4 6 3 6 6
2 1 1 3 0