Заочные олимпиады: Заочный этап

Недавно вы стали ректором одного из университетов и решили открыть в нем новую программу! На ней вы будете учить студентов спортивному программированию. Поэтому у них будут два типа занятий: спорт (чтобы развить силу рук) и программирование. Основным достоинством этой программы будет обучение в двух кампусах одновременно — по четным дням студенты будут ездить в первый кампус, а по нечетным — во второй.

Оба кампуса вашего университета устроены очень необычно: в каждом из них есть по \(n\) аудиторий, пронумерованных от \(1\) до \(n\), и по \(n - 1\) переходу между ними, при этом из любой аудитории можно добраться в любую другую по переходам.

Однако вы обнаружили, что студентам сложно ориентироваться сразу в двух кампусах, и решили упростить им жизнь. Вы решили выбрать два номера аудиторий \(u\) и \(v\) (\(u \neq v\)): в аудитории с номером \(u\) студенты будут заниматься спортом, а в аудитории с номером \(v\) — программированием. Обратите внимание, что \(u\) и \(v\) выбираются одинаковыми для обоих кампусов.

Так как вы хотите, чтобы студенты тратили меньше времени на перемещение между аудиториями, вам нужно минимизировать суммарное расстояние, которое потребуется преодолеть студентам между выбранными аудиториями в каждом из кампусов. Более формально, вам нужно найти такие номера \(u, v\), что \(d_1(u, v) + d_2(u, v)\) минимально, где \(d_1(u, v)\) — это расстояние между аудиториями \(u\) и \(v\) в первом кампусе, а \(d_2(u, v)\) — во втором. Расстоянием между аудиториями называется минимальное число переходов, через которые нужно пройти, чтобы добраться из одной аудитории в другую.

В обоих кампусах есть вход, и он ведет в аудиторию \(1\). Для всех остальных аудиторий разработан план эвакуации. В первом кампусе для \(i\)-й аудитории \(p_i\) равно номеру следующей аудитории на пути из \(i\)-й аудитории в первую. Во втором кампусе для \(i\)-й аудитории \(q_i\) равно номеру следующей аудитории на пути из \(i\)-й аудитории в первую.