Вася играет в популярную игру Gnomes of Might and Magic.
В этой игре Вася управляет королевством гномов, состоящим из нескольких замков, соединенных двусторонними дорогами. Сеть дорог королевства имеет специальный вид. В королевстве есть m главных замков: a1, a2, ... , am, которые образуют Путь Добра. Этот путь состоит из дорог между замками ai, ai + 1 (1 ≤ i < m), а так же дороги между am и a1. Никаких других дорог между замками Пути Добра нет.
Кроме того, для каждой пары соседних замков Пути Добра u и v существует ровно один Обход Зла — путь по дорогам королевства, ведущий из первого замка (u) во второй (v) и не имеющий с Путем Добра общих вершин, кроме вершин u и v. Известно, что никаких других дорог и замков в королевстве нет, то есть каждая дорога и каждый замок лежит либо на Пути Добра, либо на Обходе Зла (замки могут лежать и там, и там). Кроме того, никакие два Обхода Зла не имеют общих замков, отличных от замков Пути Добра.
В начале каждой недели в королевстве появляется один очень плохой гном, который встает на одну из дорог королевства и начинает грабить корованы, проходящие через эту дорогу. На одной дороге может скапливаться несколько очень плохих гномов. Вася бережет свои корованы, поэтому иногда отправляет Миссию Смерти из одного замка в другой.
Пусть Миссия Смерти должна попасть из замка s в замок t. Тогда она будет двигаться из замка s к замку t, уничтожая всех очень плохих гномов, находящихся на дорогах пути, по которому она следует. Вася настолько крут, что его Миссия Смерти может уничтожить любое число гномов на своем пути. Однако, Вася очень добрый, поэтому всегда выбирает такой путь между замками s и t, следуя которому придется уничтожить наименьшее число гномов. Если таких путей несколько то среди них Вася выбирает путь, содержащий наименьшее число дорог. Если и таких путей несколько, то среди них Вася выбирает лексикографически минимальный.
Помогите Васе, промоделируйте жизнь королевства в игре Gnomes of Might and Magic.
Под путем понимается последовательность замков такая, что каждая пара соседних замков пути соединена дорогой. При этом путь x1, x2, ... , xp лексикографически меньше пути y1, y2, ... , yq, если либо p < q и x1 = y1, x2 = y2, ... , xp = yp, либо существует такое число r (r < p, r < q), что x1 = y1, x2 = y2, ... , xr = yr и xr + 1 < yr + 1.
Примечание
В примере после первых 4 запросов существует только один путь из замка 1 в замок 2, не содержащий дорог с очень плохими гномами: 1 
6 3 5 2.
После того, как гном встал на дорогу (2, 5), следующая Миссия Смерти движется по пути 1 2 и уничтожает гнома, находившегося на дороге (1, 2). Следующая Миссия смерти идет по этому же пути, уже свободному от гномов.
После того, как еще один гном встал на дорогу (1, 2), следующая Миссия Смерти идет по пути 1 2 и уничтожает этого гнома.