На уроке информатики Якоб построил модель дерева из шариков и палочек. Модель соответствует некоторому дереву, состоящему из n вершин. На создание i-го шарика Якоб потратил ai минут.
Учительница будет оценивать качество модели по количеству усилий, потраченных Якобом на создание шариков. У неё нет времени рассматривать их все, поэтому она посмотрит только на k первых шариков в порядке DFS-обхода дерева. Оценкой Якоба будет минимальное ai среди k рассмотренных шаров.
У Якоба уже не хватит времени переделать модель, но он может сам выбрать корневую вершину, из которой учительница начнёт обход. Более того, для каждой вершины Якоб может переупорядочить список её соседей как захочет. Помогите Якобу определить, какую максимальную оценку он может получить.
Порядок DFS-обхода — это последовательность номеров вершин, выписанная рекурсивной процедурой DFS. Будучи вызванной от вершины v, процедура делает следующее:
- Напечатать v.
- Пройтись по списку соседей вершины v и вызвать процедуру DFS от всех из них по очереди. Не вызывать процедуру DFS от вершины u, если мы пришли в вершину v непосредственно из u.
Выходные данные
Выведите одно целое число — максимальную оценку, которую может получить Якоб, если правильно выберет корневую вершину и переупорядочит списки соседей.
Примечание
В первом примере Якоб может назначить корнем вершину 2 и переупорядочить список её соседей следующим образом: 4, 1, 5. В результате этого порядок DFS-обхода станет 2, 4, 1, 3, 5, минимальное значение ai среди первых трёх вершин равняется 3.
Во втором примере любой порядок обхода будет содержать вершину 1 на первом или втором месте, поэтому Якоб не может получить оценку больше чем 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
3 6 1 4 2
1 2
2 4
2 5
1 3
|
3
|
|
2
|
4 2
1 5 5 5
1 2
1 3
1 4
|
1
|