Сложно писать олимпиады, когда не понимаешь, как они могут помочь тебе в дальнейшем. Поэтому после очередного проигрыша дух в команде упал и желание писать олимпиадки куда-то ушло. Тренер вовремя заметил это и решил что-то предпринять – ведь он-то понимает, куда может завести участие во всех этих мероприятиях. После долгих раздумий он понял — нужно просто показать команде её перспективы! Тогда он, для простоты, представил все возможные варианты развития карьеры после участия в олимпиадах в виде корневого дерева. Каждая его вершина — некоторая должность в престижной IT-компании, а рёбра проведены между должностями только если возможен карьерный рост с одной должности на другую. Естественно, участие в олимпиадах позволяет легче продвигаться по этому дереву, и тренер поспешил показать это дерево команде!
Однако не всё так просто. Дело в том, что команда совершенно не разбирается в этих сложных должностях и переходах. Поэтому тренеру надо выбрать несколько должностей с красивыми и громкими названиями и сказать команде, что после участия в олимпиадах они могут занять эти должности. Однако и на этот выбор есть ограничение. Дело в том, что команда довольно дружна, и не хочет занимать слишком разные должности. Поэтому их необходимо выбрать так, чтобы самая высокая должность, из которой ещё можно попасть в каждую из выбранных, была как можно выше.
Помогите тренеру промотивировать ребят — найдите необходимое множество должностей.
Формально говоря, вам дано корневое дерево на N вершинах, и вам надо выбрать K вершин так, чтобы их наименьший общий предок был как можно дальше от корня.
Наименьший общий предок нескольких вершин — это такая вершина, что её расстояние от корня максимально и из неё можно добраться до любой из выбранных вершин, если идти в направлении от корня.
В первой строке входных данных вам даны два числа — N и K (1 ≤ K ≤ N ≤ 105) — количество должностей и количество должностей, которое должен найти тренер.
В следующей строке вам дано N - 1 число, каждое из которых не превосходит N. i-е из них содержит номер должности, из которой можно пойти на повышение в i + 1-ю. Должность с номером 1 считается корневой. Гарантируется, что данная структура является деревом с корнем в первой вершине.
В качестве ответа выведите единственную строчку из K чисел в произвольном порядке - номера должностей, которые должен выбрать тренер, либо - 1, если ответа не существует. Если ответов несколько, разрешается вывести любой.
5 2
5 1 1 1
5 2
9 3
6 9 1 9 4 9 4 1
4 6 2
Во втором тесте граф выглядит так:
В качестве ответа также можно вывести следующие тройки:
(5, 3, 7); (8, 4, 2); (9, 5, 7);
