10-11 класс

(Тағы да ағаштар) Төбелер саны $n$, қабырғалары екі жаққа да бағытталған ағаш берілген. Екі төбенің арасындағы арақашықтық, олардың арасындағы ең қысқа жолында жатқан қабырғалардың саны деп есептеледі. Арақашықтығы ең алыс орналасқан екі төбенің арасындағы арақашықтықты -- ағаштың диаметрі деп атайды.
Бұл есепте ең көп дегенде $k$ жою операциясын қолдану арқылы ағаштың диаметрін ықшамдау керек.
Жою операциясы -- бір төбені және оған жалғанған барлық қабырғаларды жою, сонымен қатар, төбе жойылғаннан граф байланысты болмай қалса, оны жоюға болмайды.

Кіріс деректер форматы:

Бірінші жолда $n$ және $k$ сандары ($0 \le k \le n - 1$) - төбелер саны және жоюға болатын төбелердің максималды саны.
Келесі $n-1$ жолда графтың қабырғалары берілген.
Әр жолда $u$ және $v$ сандары берілген ($1 \le u, v \le n$) - $u$ және $v$ төбелерінің арасында екі жаққа бағытталған қабырғаның бар екенін білдіреді.

Шығыс деректер форматы:

Бір сан шығарыңыз -- ағашқа ең көп дегенде $k$ жою операциясын қолдану арқылы алынған ең кіші диаметрі.

Мысалдар:

1.Мысал:

5 2
1 4
3 2
1 2
5 2

Жауап:

2

2.Мысал:

14 5
13 2
10 4
6 12
8 11
11 13
5 14
10 3
11 5
12 1
9 7
11 10
10 9
6 10

Жауап:

3

Бағалау:

Есеп 100 тесттен тұрады, әр тест 1 ұпаіға бағаланады.
Тесттердегі шектеулер:

• 10 тестте: $n \le 20$
  
• 10 тестте: $n \le 100$
  
• 5 тестте: $k = 0$
  
• 24 тестте: $n \le 2000$
  
• 51 тестте: $n \le 5000$
  

( Askhat Zhalgasov )