Problem description

Jasio żyje w państwie trójkątów. Państwo trójkątów to N-kąt foremny, w którym narysowano N − 3 nieprzecinające się przekątne, w taki sposób, że wielokąt podzielił się na N − 2 trójkąty. Miasta w państwie trójkątów są właśnie takimi trójkątami. Powiemy, że miasta są sąsiednie, jeśli pomiędzy nimi znajduje się przekątna triangulacji. Odległość między sąsiednimi miastami wynosi jeden trianmetr.

Przykładowe państwo trójkątów może wyglądać tak:

Jasio, jako przedstawiciel handlowy Januszex S.A., często musi jeździć po różnych miastach. Oczywiście, jako że firma płaci za paliwo, chciałaby optymalizować koszty, dlatego postanowiono przygotować program, który pomoże Jasiowi w planowaniu trasy i będzie wyznaczał najkrótsze trasy pomiędzy trójkątnymi miastami. Oczywiście, jak to w takich zadaniach bywa, obowiązek ten spoczywa na Tobie.

Napisz program, który: wczyta opis państwa trójkątów oraz zapytania Jasia o trasy między wybranymi parami miast, dla każdego zapytania wyznaczy długość najkrótszej trasy i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę boków państwa trójkątów. W kolejnych N − 3 wierszach znajduje się opis kolejnych przekątnych triangulacji państwa trójkątów. Opis każdej przekątnej składa się z dwóch liczb naturalnych x_i oraz y_i, oddzielonych pojedynczym odstępem. Są to numery wierzchołków na obwodzie państwa trójkątów połączonych przekątną.

W kolejnym wierszu znajduje się jedna liczba naturalna Q, określająca liczbę zapytań Jasia. W kolejnych Q wierszach znajduje się opis kolejnych zapytań Jasia. Opis każdego zapytania Jasia składa się z sześciu liczb naturalnych a_i, b_i, c_i, d_i, e_i, f_i, pooddzielanych pojedynczymi odstępami. Określają one, że Jasio chce przemieścić się między miastem rozpiętym przez odcinki w wierzchołkach (a_i,b_i,c_i) oraz miastem rozpiętym przez odcinki w wierzchołkach (d_i,e_i,f_i).

Kolejno występujące wierzchołki na obwodzie państwa trójkątów numerowane są kolejnymi liczbami naturalnymi od 1 do N. Możesz założyć, że dane wejściowe są poprawne.

Wyjście

Twój program powinien wypisać na wyjście Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania Jasia – odległość między miastami z zapytania wyrażona w trianmetrach.

Ograniczenia

3 ≤ N ≤ 100 000, 1 ≤ Q ≤ 100 000.

Przykład

6
1 3
6 3
4 6
2
1 2 3 4 5 6
6 1 3 3 4 6

3
1