Processing math: 100%

Задача E. Удлинители

Автор:А. Кленин, М. Спорышев, С. Суренков, Д. Давидюк   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

В каждом удлинителе имеется K разъёмов, так что к нему можно подключить не более K других удлинителей.

Назовём электрическим расстоянием от удлинителя до розетки количество удлинителей, которые должен пройти электрический ток от данного удлинителя до розетки.

Такой способ организации электрической сети является очень ненадёжным. Особенно подвержены сбоям удлинители, электрическое расстояние от которых до розетки велико.

Требуется написать программу, которая по данному описанию электрической сети из удлинителей переключит один из удлинителей (т. е. выдернет его из удлинителя, в который он был включен, и подключит к какому-нибудь удлинителю) таким образом, чтобы максимальное среди всех удлинителей электрическое расстояние стало наименьшим возможным.

Формат входного файла

Входной файла содержит целые числа N K, за которыми следуют N чисел pi, где pi — номер удлинителя, к которому подключен i-й удлинитель, i=1N. К розетке подключен удлинитель номер 0.

Формат выходного файла

Выходной файл должен содержать два целых числа S T, означающие, что удлинитель номер S следует отключить от удлинителя номер pS и подключить к удлинителю номер T. Если оптимальных решений несколько, выведите любое из них.

Ограничения

1N100000, 0piN, 2K100000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 2
0 1 2 1 6 0
3 6
2
1 5
0
1 0

0.056s 0.008s 13