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

\begin{document}
	
\renewcommand{\tl}{$0.5$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача А2. ТРАНСПОРТ}
\addauthor{Автор: Илиян Йорданов}{2026}{02}{14}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	Областен кръг, 14 февруари 2026 г.\\
	Група A – 11, 12 клас
}

След поредните стачки и спиране на градския транспорт в град Олимпово на държавата Олимпия, управниците на града взеха решение да направят цялостна реорганизация на транспорта в срок до предстоящите празници. Нелеката задача за това беше възложена отново на \textbf{Д}ени. Пътната мрежа на Олимпово се състои от $N$ спирки, удобно номерирани с числата от $1$ до $N$, които са свързани с $N-1$ \textbf{еднопосочни} улици, така че от спирка $1$ може да се стигне до всички останали. Може да се покаже, че такава пътна мрежа има свойството, че ако има път между две спирки чрез улиците (евентуално минавайки и през други спирки), то той е единствен.

Реорганизацията на транспорта се състои в това да се изготви изцяло нов план за линиите на градския транспорт, така че през всяка спирка да минава поне една линия, за да се осигури свързаност. Общинските съветници предложили общо $K$ варианта за линии на градския транспорт. Всяка линия представлява път между две спирки, като се започва от първата спирка и движейки се по улиците, се достига до втората спирка (евентуално преминавайки през други спирки по пътя).

\textbf{Д}ени искала да убеди съветниците, че има прекалено много направени предложения. Затова тя ще преброи всички възможности за избиране на някои от предложените варианти (може и всички $K$ варианта), така че през всяка спирка да минава поне една линия, с което като бонус ще спечели и сърцето на кмета. Напишете програма \textbf{\texttt{transport}}, която по данни за пътната мрежа и направените предложения, намира търсения брой възможности от \textbf{Д}ени. Понеже броят може да е много голям, то търсим само остатъка му по модул $10^9+7$.

\subsection{Вход}
От първия ред на стандартния вход се въвежда цялото число $N$ -- брой спирки. От следващите $N-1$ реда се въвеждат по две цели числа  $x_i \ y_i$, които задават еднопосочна улица от спирка $x_i$ към спирка $y_i$.

От следващия ред се въвежда цялото число $K$ -- брой предложени варианти за линии на градския транспорт. От последните $K$ реда се въвеждат по две цели числа $s_j \ e_j$, които задават линия на градския транспорт, започваща от спирка $s_j$ и завършваща в спирка $e_j$. Гарантирано е, че винаги има единствен път по улиците от спирка $s_j$ до $e_j$, като е възможно да има дублиращи се предложения за линии.

\subsection{Изход}
Отпечатайте едно число по модул $10^9+7$, равно на общия брой възможности за избиране на някои от предложените варианти за осигуряване на поне една линия през всяка спирка.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \le N \le 5~000$
	\item $1 \le K \le 200~000$
\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{\makecell{Необходими\\подзадачи}} & $N$ & $K$ & \textbf{Други ограничения} \\
		\hline
		$0$ & $0$ & $-$ & $-$ & $-$ & Примерът. \\ 
		\hline
		$1$ & $7$ & $0$ & $\le 10$ & $\le 18$ & \SetCell[r=2]{}{--} \\ 
		\hline
		$2$ & $6$ & $0-1$ & $\le 50$ & $\le 22$ & \\
		\hline
		$3$ & $11$ & $-$ & $\le 700$ & $\le 700$ & \SetCell[r=3]{}{Има път, който включва всички улици, като $x_i = i$ и $y_i = i+1$ за всяко $i = 1, 2, \dots, N-1$.} \\ 
		\hline
		$4$ & $12$ & $3$ & $\le 3~000$ & $\le 3~000$ & \\ 
		\hline
		$5$ & $13$ & $3-4$ & $\le 3~000$ & $\le 200~000$ & \\ 
		\hline
		$6$ & $11$ & $-$ & $\le 5~000$ & $\le 200~000$ & От спирка $1$ има улица до всяка друга спирка. \\ 
		\hline
		$7$ & $19$ & $0-3$ & $\le 700$ & $\le 700$ & \SetCell[r=2]{}{--} \\
		\hline
		$8$ & $21$ & $0-7$ & $\le 5~000$ & $\le 200~000$ & \\
		\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]{
				6\\
				1 2\\
				2 3\\
				2 4\\
				1 5\\
				5 6\\
				6\\
				1 3\\
				1 4\\
				5 6\\
				1 5\\
				1 5\\
				2 3
		}}
		&
		\texttt{12}
		& 
		{\begin{minipage}[t]{\linewidth}
				Илюстрация на пътната мрежа в Олимпово:\\
				\begin{adjustbox}{width=0.35\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
					\includesvg[inkscapelatex=false]{graph}
				\end{adjustbox}
				Спирките, през които преминават предложените варианти за линии, са следните:\\
				\tabitem $1 \to 2 \to 3$;\\
				\tabitem $1 \to 2 \to 4$;\\
				\tabitem $5 \to 6$;\\
				\tabitem $1 \to 5$;\\
				\tabitem $1 \to 5$;\\
				\tabitem $2 \to 3$.\\
				Има $12$ възможности за осигуряване на поне една линия през всяка спирка, като се изберат следните варианти за линии (вариантите са номерирани с римски числа):
				\vspace{-\baselineskip}
				\begin{multicols}{2}
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{4};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{5};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{6};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{4}, \Romanbar{5};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{4}, \Romanbar{6};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{5}, \Romanbar{6};\\
					\tabitem \Romanbar{1}, \Romanbar{2}, \Romanbar{3}, \Romanbar{4}, \Romanbar{5}, \Romanbar{6};\\
					\tabitem \Romanbar{2}, \Romanbar{3}, \Romanbar{6};\\
					\tabitem \Romanbar{2}, \Romanbar{3}, \Romanbar{4}, \Romanbar{6};\\
					\tabitem \Romanbar{2}, \Romanbar{3}, \Romanbar{5}, \Romanbar{6};\\
					\tabitem \Romanbar{2}, \Romanbar{3}, \Romanbar{4}, \Romanbar{5}, \Romanbar{6}.
				\end{multicols}
		\end{minipage}} \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}