Однажды Васе в руки попалось бумажное письмо в конверте. Вася знает, что когда работники Берляндской почты пересылают письмо напрямую из города «A» в город «B» они ставят на него либо штамп «A B», либо «B A». К сожалению, часто невозможно напрямую переслать письмо из города отправителя в город получателя, поэтому письмо пересылается через некоторые промежуточные города. Работники почты никогда не пересылают письмо по циклу, то есть письмо не может побывать в одном городе дважды. Вася уверен, что при каждой пересылке они исправно ставят штампы.

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