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