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

\begin{document}

\renewcommand{\tl}{$4$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача GT13. ДВА ПЪТЯ}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 24 юни 2026 г.\\
	Група G
}

\centerline{Кой не обича дървета? \emoji{smile}}

Можем да опишем железопътната мрежа на БДЖ като кореново дърво с $N$ върха и корен във връх $1$ -- Варна (все пак Варна е крайната точка на първата жп линия в България). Има общо $K$ маршрута между някои двойки върхове, които се обслужват от влакове. Всеки маршрут представлява прост път в дървото. Както на всички е известно, железопътната мрежа е много стара и в окаяно състояние. Затова е важно първо да се открият най-натоварените участъци. Напишете програма \textbf{\texttt{twopaths}}, която по данните за кореновото дърво и крайните точки на маршрутите, намира два маршрута, за които повтарящите се ребра между тях са максимално много от всички възможни двойки маршрути.

\subsection{Вход}
От първия ред на стандартния вход се въвеждат естествените числа $N$ и $K$ -- броят върхове в дървото и броят маршрути. От следващия ред се въвеждат $N-1$ числа $p_2, p_3, \dots, p_N$, където $p_i$ е бащата на връх $i$. От последните $K$ реда се въвеждат по две числа $x$ и $y$, които задават началната и крайната точка на съответния маршрут. Гарантирано е, че $x \neq y$.

\subsection{Изход}
На първия ред отпечатайте намерения максимален брой съвпадащи ребра измежду всички двойки маршрути. На втория ред изведете две числа -- номерата (спрямо реда във входа) на два маршрута, за които се достига изведената стойност. Ако има повече от една възможна двойка маршрути с максимален брой съвпадащи ребра, изведете която и да е от тях.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $2 \leq N, K \leq 2.10^5$
\end{itemize}

\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$ & $9$ & $0$ & $\leq 10^2$ & $\leq 10^2$ & $-$ \\ 
		\hline
		$2$ & $7$ & $0-1$ & $\leq 4.10^3$ & $\leq 10^3$ & $-$ \\ 
		\hline
		$3$ & $11$ & $0-2$ & $\leq 10^5$ & $\leq 10^3$ & $-$ \\ 
		\hline
		$4$ & $12$ & $0-3$ & $\leq 10^5$ & $\leq 5.10^3$ & $-$ \\
		\hline 
		$5$ & $7$ & $0$ & $\leq 10^5$ & $\leq 5.10^4$ & Дървото е с височина до $20$. \\
		\hline
		$6$ & $7$ & $-$ & $\leq 10^5$ & $\leq 5.10^4$ & Всеки маршрут е част от път между корена и някое листо. \\
		\hline
		$7$ & $36$ & $0-6$ & $\leq 10^5$ & $\leq 5.10^4$ & $-$ \\
		\hline
		$8$ & $11$ & $0-7$ & $\leq 2.10^5$ & $\leq 2.10^5$ & $-$ \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{width=0.6\textwidth,
			colspec={|l|l|X[j]|}}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{
			4 2\\
			1 2 2\\
			1 3\\
			1 4
		}}
		& 
		\texttt{\makecell[lt]{
			1\\
			2 1
		}}
		& 
		{\begin{adjustbox}{width=0.15\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
				\includesvg[inkscapelatex=false]{tree1}
		\end{adjustbox}} \\
		\hline
		\texttt{\makecell[lt]{
			4 2\\
			1 2 3\\
			1 2\\
			3 4
		}}
		& 
		\texttt{\makecell[lt]{
			0\\
			1 2
		}}
		&
		{\begin{adjustbox}{width=0.043\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
				\includesvg[inkscapelatex=false]{tree2}
		\end{adjustbox}} \\
		\hline
		\texttt{\makecell[lt]{
			7 3\\
			1 2 2 4 5 5\\
			1 3\\
			3 7\\
			6 1
		}}
		& 
		\texttt{\makecell[lt]{
			2\\
			2 3
		}}
		&
		{\begin{adjustbox}{width=0.17\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
				\includesvg[inkscapelatex=false]{tree3}
		\end{adjustbox}} \\
		\hline
		\texttt{\makecell[lt]{
			4 3\\
			1 2 3\\
			1 4\\
			4 1\\
			1 4
		}}
		& 
		\texttt{\makecell[lt]{
			3\\
			2 1
		}}
		&
		{\begin{adjustbox}{width=0.06\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
			\includesvg[inkscapelatex=false]{tree4}
		\end{adjustbox}} \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}