Валера наконец-то решил отдохнуть! Он собрал все свои вещи и отправился на горнолыжный курорт.
Валера решил прокатиться на лыжах, однако понял, что плохо ориентируется на местности. Ему подсказали, что на курорте есть n объектов (будем считать, что объекты пронумерованы некоторым образом числами от 1 до n), и каждый из объектов является либо отелем, либо горой.
Валера разузнал, что на горнолыжном курорте построено несколько лыжных дорожек. А именно, для каждого объекта v на курорте существует не более одного объекта u такого, что из объекта u построена лыжная дорожка, ведущая в объект v. Известно, что не существует такого отеля, из которого построена лыжная дорожка, ведущая в некоторый объект.
Валера боится потеряться на курорте, поэтому он хочет, чтобы Вы предложили для его лыжной прогулки маршрут из объектов v1, v2, ..., vk (k ≥ 1) такой, что:
- Объекты с номерами v1, v2, ..., vk - 1 — горы, а объект с номером vk — отель.
- Для любого целого i (1 ≤ i < k) из объекта с номером vi построена ровно одна лыжная дорожка. Эта дорожка должна вести в объект vi + 1.
- В маршруте как можно больше объектов (k максимально).
Помогите Валере. Найдите такой маршрут, который удовлетворит всем критериям нашего героя!
Выходные данные
В первой строке выведите k — максимальную возможную длину маршрута для Валеры. Во второй строке выведите k целых чисел v1, v2, ..., vk — сам маршрут.
Если существует несколько решений, разрешается вывести любое.