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

\begin{document}

\renewcommand{\tl}{$1.2$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача C2. DISPATCH}
\addauthor{Автор: Добрин Башев}{2026}{06}{15}
\renewcommand{\header}{
    НАЦИОНАЛЕН ЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА\\
 \vspace{0.1cm}
    \textbf{Пловдив, 12 - 14 юни  2026 г.}\\
    \vspace{0.1cm}
    \textbf{Група C -- 7, 8 клас}
}


Логистичната мрежа на компанията „СкайФрейт“ се състои от $n$ разпределителни центъра (хъба), които са свързани помежду си с $n-1$ двупосочни въздушни трасета. Мрежата е проектирана изключително ефективно, което означава, че между всеки два разпределителни центъра съществува единствен път по въздушните трасета (т.е. структурата на мрежата е дърво).

Компанията е идентифицирала $m$ високоприоритетни заявки за доставка за предстоящата работна смяна, номерирани с целите числа от $1$ до $m$. Заявката с номер $i$ се състои в това даден дрон да вземе пратка от център $a_i$ и да я достави в друг център $b_i$. 

От „СкайФрейт“ планират да позиционират един главен диспечерски дрон в някой от разпределителните центрове $x$. За да се минимизира износването на батерията му, главният дрон може да обслужи дадена заявка между $a_i$ и $b_i$ тогава и само тогава, ако може, излитайки от своята начална станция $x$, да прелети през абсолютно всички центрове по уникалния път между $a_i$ и $b_i$ в рамките на едно непрекъснато пътуване, без нито веднъж да преминава през едно и също въздушно трасе повторно.

Напишете програма \texttt{\textbf{dispatch}}, която намира максималния брой заявки за доставка, които могат да бъдат обслужени, ако „СкайФрейт“ избере най-подходящия център $x$ за разполагане на главния дрон.


\subsection{Вход}
От първия ред на стандартния вход се въвежда едно цяло число $n$ -- броят на разпределителните центрове в мрежата.

В следващите $n-1$ реда са описани въздушните трасета. Всяко трасе се задава с две цели числа $x_i$ и $y_i$ -- номерата на центровете, които то свързва директно.

На следващия ред се въвежда едно цяло число $m$ -- броят на планираните заявки за доставка.

В следващите $m$ реда са описани самите заявки. На $i$-тия от тях са зададени две различни цели числа $a_i$ и $b_i$ -- съответно началният център за вземане и крайният център за доставка на $i$-тата заявка. Заявките могат да се застъпват, пресичат или напълно да съвпадат. Центровете в мрежата се номерират от 1 до $n$.

\subsection{Изход}
На стандартния изход програмата трябва да изведе едно единствено цяло число -- максималния брой заявки за доставка, които главният дрон може да изпълни, ако бъде зает най-оптималният разпределителен център $x$.


\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
    \item $2 \le n \le 2 \cdot 10^5$
    \item $1 \le m \le 2 \cdot 10^5$
    \item $1 \le x_i, y_i, a_i, b_i \le n$
    \item $a_i \ne b_i$
  \end{itemize}  

\subsection{Подзадачи}
\begin{table}[H]
    \begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
        \hline
        \textbf{Подзадача} & \textbf{Точки} & \textbf{Допълнителни ограничения} \\
        \hline
        $0$ & $0$ & Тестовете от условието. \\
        \hline
        $1$ & $23$ & $n, m \le 200$  \\ 
        \hline
        $2$ & $33$ & $n, m \le 5000$  \\ 
        \hline
        $3$ & $44$ & Без допълнителни ограничения.  \\ 
        \hline
    \end{tblr}
\end{table}
  
  
\subsection{Пример}
\begin{table}[H]
    \begin{tblr}{|l|l|X[l,t]|}
        \hline
        \textbf{Вход} & \textbf{Изход} & \textbf{Обяснение} \\
        \hline
        \texttt{\makecell[lt]{7\\
1 2\\
2 3\\
3 4\\
3 5\\
5 6\\
5 7\\
3\\
1 5\\
2 4\\
6 7
\\ }}
        & 
        \texttt{\makecell[lt]{2\\
        }}
        &
        \begin{minipage}[t]{\linewidth}
        Ако главният диспечерски дрон бъде разположен в център $1$, той ще може да обслужи първите две заявки за доставка: $(1, 5)$ и $(2, 4)$. \\ 
            -- За заявката $(1, 5)$ дронът излита от $1$ и изпълнява непрекъснат полет $1 \to 2 \to 3 \to 5$, преминавайки през трасетата $(1, 2)$, $(2, 3)$ и $(3, 5)$ точно по веднъж. \\
            -- За заявката $(2, 4)$ изискваният път е $2 \to 3 \to 4$. Тъй като стартира от $1$, дронът лети по траекторията $1 \to 2 \to 3 \to 4$ през трасетата $(1, 2)$, $(2, 3)$ и $(3, 4)$ -- всички необходими центрове са обходени, а трасетата са използвани само по веднъж без нито едно дублиране. \\
        Максималният резултат от $2$ обслужени заявки може да бъде постигнат също така, ако дронът се позиционира в център $6$ (изпълнявайки заявките $(1, 5)$ и $(6, 7)$) или в център $7$.
        \end{minipage}
\\
        \hline 
    \end{tblr}
\end{table}
\FloatBarrier
    
\end{document}