Відстань на триангуляції
Маємо правильний багатокутник, вершини якого пронумеровані від 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-го запиту. Гарантовано, що жодна діагональ не збігається зі стороною багатокутника, і жодні дві діагоналі не збігаються та не перетинаються.
Вихідні дані
Для кожного запиту виведіть в окремому рядку найкоротшу відстань.
