Друзья Вася и Петя живут в Бертауне. В этом городе n перекрестков, некоторые из которых соединены одинаковыми по длине двунаправленными улицами. Вася живет в доме на перекрестке номер 1, а Петя — в доме на перекрестке номер n.

Однажды Вася и Петя поссорились так сильно, что отказывались даже видеть друг друга. Так уж вышло, что сегодня Васе нужно дойти от своего дома до перекрестка n, а Пете — от своего дома до перекрестка 1. При этом они не хотят встречаться ни на одном перекрестке, но вполне допустимо, если они встретятся в середине улицы, проходя ее в противоположных направлениях. Вася и Петя попросили вас, как их общего друга, помочь им справиться с этой непростой задачей.

Найдите для Васи и Пети такие маршруты с одинаковым числом улиц, чтобы ребята, следуя маршрутам, никогда не оказывались одновременно на одном перекрестке. Встречаться в середине улицы, двигаясь навстречу друг другу, они могут (см. пример 1). Среди всех возможных маршрутов выберите такой, что количество улиц в нем как можно меньше. Пока оба одновременно не дошли до своих целей, ребята не могут стоять на месте.

Вася и Петя двигаются одновременно и с одинаковой скоростью, то есть допустима ситуация, когда один из них приходит к некоторому перекрестку, а другой уходит из него же. Например, Вася может пойти от перекрестка 1 к перекрестку 2, а Петя может в то же время пойти от перекрестка 2 к перекрестку 3.

Если маршрутов, удовлетворяющих всем требованиям, не существует, ваша программа должны выводить -1.