Triangulyasiya üzrə məsafə
Düzgün çoxbucaqlı verilib. Çoxbucaqlının təpələri ardıcıl olaraq 1-dən n-ə qədər nömrələnib. Həmçinin, bu çoxbucaqlının n − 3 diaqonallardan ibarət olan üçbucaqlanması verilib.
q sorğu verilib. Hər bir sorğu iki təpənin nömrələri ilə verilir. Hər bir sorğu üçün bu iki təpə arasında ən qısa məsafəni tapın, çoxbucaqlının tərəfləri və ya verilmiş diaqonalları boyunca hərəkət edərək, məsafə keçilən tərəflərin və diaqonalların ümumi sayına bərabərdir.
Giriş məlumatları
Birinci sətir çoxbucaqlının təpələrinin sayını n (4 ≤ n ≤ 50 000) ehtiva edir.
Növbəti n − 3 sətirin hər biri i-ci diaqonalın ucları olan iki ədəd a[i], b[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i]) ehtiva edir.
Növbəti sətir sorğuların sayını q (1 ≤ q ≤ 100 000) ehtiva edir.
Növbəti q sətirin hər biri i-ci sorğunun təpələri olan iki tam ədəd x[i], y[i] (1 ≤ x[i], y[i] ≤ n) ehtiva edir. Zəmanət verilir ki, heç bir diaqonal çoxbucaqlının tərəfi ilə üst-üstə düşmür və heç bir iki diaqonal üst-üstə düşmür və kəsişmir.
Çıxış məlumatları
Hər bir sorğu üçün ayrıca sətirdə ən qısa məsafəni çıxarın.