Triangulyasiyada Məsafə#7564
Verilmiş səthli düzgün çoxbucaq. Çoxbucağın zirvələri -dən -ə qədər düz bir sıra ilə nömrələnmişdir. Həmçinin bu çoxbucağın n - 3 diaqonal siyahısı şəklində verilməsi ilə triangulyasiyası təqdim olunur.
qədər sorğu verilir. Hər bir sorğu iki zirvə nömrəsindən ibarətdir. Hər bir sorğu üçün həmin zirvələr arasında çoxbucağın kənarları və ya verilən diaqonallar üzrə hərəkət edərək ən qısa məsafəni müəyyənləşdirmək lazımdır. Məsafə keçilən kənarların və diaqonalların ümumi sayı kimi müəyyən edilir.
Birinci sətir çoxbucağın zirvələrinin sayını ifadə edən bütöv ədəd n~(4 \le n \le 50000) dəyərini ehtiva edir.
Növbəti n - 3 sətir hər biri iki ədəddən a_i, b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) ibarət olmaqla -ci diaqonalların uclarını ehtiva edir.
Növbəti sətir sorğuların sayını əks etdirən bütöv ədəd q~(1 \le q \le 10^5) verir.
Növbəti sətir hər biri iki ədəd x_i, y_i (1 \le x_i, y_i \le n) olan -ci sorğu zirvələrini göstərir.
Qaranti edilir ki:
Hər hansı bir diaqonal çoxbucağın kənarı ilə üst-üstə düşmür;
Heç bir iki diaqonal üst-üstə düşmür və kəsişmir.
Hər sorğu üçün müvafiq bir sətirdə verilmiş zirvələr arasında olan ən qısa məsafəni ifadə edən bir ədəd yazın.
Nümunə 1