| Автор: | А. Кленин, М. Спорышев, С. Суренков, Д. Давидюк | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
В компьютерном классе имеется одна розетка. Для того, чтобы подключить к ней компьютеры, используется N + 1 удлинителей. Один из удлинителей включается розетку, а каждый из остальных N — в другой удлинитель. При этом гарантируется, что каждый удлинитель в конце концов подключен к розетке.
В каждом удлинителе имеется K разъёмов, так что к нему можно подключить не более K других удлинителей.
Назовём электрическим расстоянием от удлинителя до розетки количество удлинителей, которые должен пройти электрический ток от данного удлинителя до розетки.
Такой способ организации электрической сети является очень ненадёжным. Особенно подвержены сбоям удлинители, электрическое расстояние от которых до розетки велико.
Требуется написать программу, которая по данному описанию электрической сети из удлинителей переключит один из удлинителей (т. е. выдернет его из удлинителя, в который он был включен, и подключит к какому-нибудь удлинителю) таким образом, чтобы максимальное среди всех удлинителей электрическое расстояние стало наименьшим возможным.
Входной файла содержит целые числа N K, за которыми следуют N чисел pi, где pi — номер удлинителя, к которому подключен i-й удлинитель, i = 1… N. К розетке подключен удлинитель номер 0.
Выходной файл должен содержать два целых числа S T, означающие, что удлинитель номер S следует отключить от удлинителя номер pS и подключить к удлинителю номер T. Если оптимальных решений несколько, выведите любое из них.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|