Відстань на триангуляції#7564
Дано правильний багатокутник з вершинами. Вершини багатокутника пронумеровані послідовно числами від до . Також задано триангуляцію цього багатокутника у вигляді списку з n - 3 діагоналей.
Дано запитів. Кожен запит задається номерами двох вершин. Для кожного запиту необхідно визначити найкоротшу відстань між цими вершинами, переміщуючись по сторонах або по заданим діагоналям багатокутника. Відстань визначається як загальна кількість пройдених сторін і діагоналей.
Перша строка містить ціле число n~(4 \le n \le 50\,000) — кількість вершин багатокутника.
Наступні n - 3 строки містять по два числа a_i, b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) — кінці -ї діагоналі.
Наступна строка містить ціле число q~(1 \le q \le 10^5) — кількість запитів.
Наступні строки містять по два числа x_i, y_i (1 \le x_i, y_i \le n) — вершини -го запиту.
Гарантовано, що:
жодна діагональ не збігається зі стороною багатокутника;
жодні дві діагоналі не збігаються і не перетинаються.
Для кожного запиту виведіть в окремому рядку одне число — найкоротшу відстань між вказаними вершинами.
Приклад 1