\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\newcommand{\msg}[2]{#1 \rightarrow #2}

\begin{document}
	
	\renewcommand{\tl}{$0.3$ сек.}
	\renewcommand{\ml}{$256$ MB}
	\problem{Задача C3. СЪОБЩЕНИЕ}
	\renewcommand{\header}{
		XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
		Областен кръг, 14 февруари 2026 г.\\
		Група C – 7, 8 клас
	}
	
	Кирчо има $N$ международни приятеля, номерирани с числата от $1$ до $N$. Някои от тях се познават, като познанството между тях е взаимно, тоест ако приятел $i$ познава приятел $j$, то приятел $j$ задължително познава приятел $i$. Кирчо има много важно съобщение, което всеки негов приятел трябва да получи. За целта Кирчо и всеки от неговите приятели може да препраща съобщението до негови познати\footnote{Счита се, че Кирчо познава всеки от приятелите си.}. В тази задача е гарантирано, че съобщение може да стигне от всеки до всеки по точно един начин. Формално, графът, образуван от познанствата между $N$-те приятеля, представлява дърво\footnote{Дърво е ацикличен свързан неориентиран граф. В частност, ако дърво има $N$ върха, е гарантирано, че има точно $N-1$ ребра.}.
	
	Понеже роуминг таксите са неособено високи, Кирчо може да препрати съобщението на най-много един негов приятел, и денят, в който го праща, се счита за ден 0. Останалото препращане се извършва по следното правило - ако някой приятел е получил съобщение в ден $d$, то във всеки следващ ден ($d + 1$, $d + 2$, $\dots$) той има право да препрати съобщението на най-много $K$ негови познати. Забележете, че ако някой приятел получи съобщението повече от веднъж, той не може да го препрати повече от $K$ пъти в един и същ ден.
	
	Кирчо се чуди колко най-малко дни трябва да минат, за да е получил всеки приятел съобщението. Понеже Кирчо не може да се справи сам, Ви моли да му помогнете, като напишете програма \textbf{\texttt{message}}, която намира търсената ширина.
	
	\subsection{Вход}
	От първия ред на стандартния вход се въвеждат целите положителни числа $N$ и $K$ - броят международни приятели на Кирчо и максималният брой познати, на които могат да се препрати съобщението в един ден. От следващите $N-1$ реда се въвеждат по две числа $u_i$ и $v_i$, описващи познанствата - това означава, че приятелите с номера $u_i$ и $v_i$ се познават взаимно.
	
	\subsection{Изход}
	На един ред на стандартния изход изведете едно число - минималния брой дни.
	
	\subsection{Ограничения}
	\vspace{0.1em}
	\begin{itemize}
		\item $1 \leq N, K \leq 10^5$
		\item $1 \leq u_i, v_i \leq N$
		\item $u_i \neq v_i$
		\item Гарантирано е, че графът, образуван от познанствата, е свързан.
	\end{itemize}
	
	\newpage
	\subsection{Подзадачи}
	\begin{table}[H]
		\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
			\hline
			\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N$ & $K$ & \textbf{Други ограничения}\\
			\hline
			$0$ & $0$ & $-$ & $-$ & $-$ & Примерният тест. \\ 
			\hline
			$1$ & $13$ & $-$ & $\leq 9$ & $-$ & $-$ \\ 
			\hline
			$2$ & $5$ & $-$ & $-$ & $-$ & Съществува приятел, който се познава с всеки друг. \\ 
			\hline
			$3$ & $8$ & $-$ & $-$ & $-$ & Всеки приятел има най-много двама познати, като изключим Кирчо. \\ 
			\hline
			$4$ & $13$ & $-$ & $-$ & $= N$ & $-$ \\
			\hline 
			$5$ & $21$ & $0$ & $\leq 2000$ & $= 1$ & $-$ \\
			\hline 
			$6$ & $19$ & $0-1,5$ & $\leq 2000$ & $-$ & $-$ \\
			\hline 
			$7$ & $21$ & $0-6$ & $-$ & $-$ & $-$ \\
			\hline
		\end{tblr}
		\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
	\end{table}
	\FloatBarrier
	
	\subsection{Пример}
    \begin{table}[H]
    	\begin{tblr}{|l|l|X[j]|}
    		\hline
    		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
    		\hline
    		\texttt{\makecell[lt]{14 1 \\
					1 2 \\
					1 3 \\
					3 4 \\
					4 5 \\
					3 6 \\
					6 7 \\
					6 8 \\
					8 9 \\
					9 10 \\
					9 11 \\
					2 12 \\
					2 13 \\
					12 14}}
    		& 
    		\texttt{\makecell[lt]{5}}
    		& 
    		{
    		Нека Кирчо прати съобщението на приятел $3$. Тогава може препращането да се състои, както следва: \\
            Ден $1$: $\msg{3}{6}$ \\
            Ден $2$: $\msg{3}{1}$, $\msg{6}{8}$ \\
            Ден $3$: $\msg{3}{4}$, $\msg{1}{2}$, $\msg{8}{9}$ \\
            Ден $4$: $\msg{4}{5}$, $\msg{2}{12}$, $\msg{9}{11}$ \\
            Ден $5$: $\msg{9}{10}$, $\msg{2}{13}$, $\msg{12}{14}$, $\msg{6}{7}$ \\
            Може да се докаже, че не може да се постигне целта на Кирчо с по-малко от $5$ дни.}\\
    		\hline
    	\end{tblr}
    \end{table}
    \FloatBarrier
	
\end{document}