Однажды Васе в руки попалось бумажное письмо в конверте. Вася знает, что когда работники Берляндской почты пересылают письмо напрямую из города «A» в город «B» они ставят на него либо штамп «A B», либо «B A». К сожалению, часто невозможно напрямую переслать письмо из города отправителя в город получателя, поэтому письмо пересылается через некоторые промежуточные города. Работники почты никогда не пересылают письмо по циклу, то есть письмо не может побывать в одном городе дважды. Вася уверен, что при каждой пересылке они исправно ставят штампы.
На конверте Васиного письма n почтовых штампов. Он понимает, что возможных маршрута следования письма всего два. Но штампов очень много, и Вася не может сам определить ни один из этих маршрутов. Поэтому он просит вас помочь ему. Найдите один из возможных маршрутов следования письма.
Выходные данные
Выведите n + 1 число — номера городов в одном из двух возможных маршрутов в порядке следования письма.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 100
100 2
|
2 100 1
|
|
2
|
3
3 1
100 2
3 2
|
100 2 3 1
|