Дано дерево, состоящее из n вершин. Вершины пронумерованы от 1 до n.
Определим длину отрезка [l, r] величиной r - l + 1. Счет поддерева данного дерева равняется максимальной длине такого отрезка [l, r], что вершины с номерами l, l + 1, ..., r принадлежат поддереву.
Рассмотрим все поддеревья данного дерева размером не больше k, выведите максимальный счет поддерева среди рассматриваемых. Обратите внимание, что в данной задаче дерево не корневое, поэтому поддерево — это любой связный подграф дерева.
Выходные данные
Выведите единственное целое число — максимальный возможный счет.
Примечание
В первом примере имеется поддерево размера не больше 6, включающее тройку последовательных номеров вершин. Например, поддерево, состоящее из {1, 3, 4, 5, 7, 8} или из {1, 4, 6, 7, 8, 10}, включает тройку последовательных номеров вершин. Однако не существует поддерева, размер которого не больше 6, включающего 4 или более последовательных номеров вершин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 6
4 10
10 6
2 9
9 6
8 5
7 1
4 7
7 3
1 8
|
3
|
|
2
|
16 7
13 11
12 11
2 14
8 6
9 15
16 11
5 14
6 15
4 3
11 15
15 14
10 1
3 14
14 7
1 7
|
6
|