% !TeX program=lualatex

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

\begin{document}
	
\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача D2. ОЦВЕТЯВАНЕ}
\addauthor{Автор: Иван Лупов}{2026}{06}{15}
\renewcommand{\header}{
	НАЦИОНАЛЕН ЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА\\
	Пловдив, 12 -- 14 юни 2026 г.\\
	Група D -- 6 клас
}

Обикновено, бабите решават пъзели судоку или кръстословици във вестниците, за да разнообразят времето, но баба Яна е особена в това, че нейната предпочитана главоблъсканица е да оцветява графи. 

Граф $G$ наричаме множесто от \textit{върхове}, свързани с \textit{ребра} помежду им. Забележете, че графите могат да не са \textit{свързани} -- на примера по-долу върхове $6$ и $7$ са отделени от всички останали и нямат ребра към тях, но имат едно ребро помежду си. Свързано подмножество от върхове, към което не могат да се добавят повече върхове, ще наричаме \textit{компонента}. Примерно, на долния пример върхове $6$ и $7$ образуват една компонента, а всички останалите -- друга компонента.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.3\textwidth]{graph_1.png}
	\caption{Примерен граф}
\end{figure}

За да не стават графите в пъзелите на баба Яна грозни, те винаги имат най-много едно ребро между двойка върхове и няма ребро, което да свързва връх със самия него. Допълнително особеност на графите, с които баба Яна работи е, че за всеки връх $u$ има стойност $a_u$, която ще наричаме награда.

Пъзелът на баба Яна се състои в следното: тя трябва да оцвети върховете на графа в два цвята: червен и син. Общата награда, която ще получи бабата е равна на сумата от наградите за върховете, оцветени в червено. Има обаче една уловка! За всяко ребро е забранено двата върха, които то свързва да са оцветени в еднакъв цвят -- единият от тях трябва да е червен, а другият син, задължително.

Напишете програма \textbf{\texttt{coloring.cpp}}, която намира максималната печалба, която баба Яна може да натрупа. Понеже авторите на пъзелите понякога правят грешки, Вашата програма трябва да може допълнително да засича, когато пъзелът е нерешим -- в такъв случай трябва да изведете числото \texttt{-1}.

\subsection{Вход}

На първия ред на стандартния вход се въвеждат $n$ и $m$ -- броят на върхове в графа и броят на ребрата помежду им. На втория ред на стандартния вход се въвеждат стойностите $a_1, a_2, \dots, a_n$ -- печалбата, която ще получим, ако оцветим $i$-тия връх в червено за $i = 1, 2, \dots n$. На следващите $m$ реда се въвеждат двойки $u_j, v_j$, които описват по едно ребро.

\subsection{Изход}

Ако пъзелът може да бъде решен, тоест съществува коректно оцветяване на върховете, такова че за всяко ребро двете му краища са оцветени в различни цветове, изведете максималната сума на наградите на червените върхове. В противен случай, изведете \texttt{-1}.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \le n \le 2 \times 10^5$
	\item $1 \le m \le 4 \times 10^5$
	\item $1 \le a_i \le 10^4$ за $i=1,2,\dots,n$
	\item $1 \le u_j, v_j \le n$ за $j=1,2,\dots,m$
	\item Между всяка двойка върхове има най-много едно ребро.
	\item Не съществува ребро, за което $u_j = v_j$.
	\item Графът може да се състои от няколко компоненти, някои от които да съдържат единствен връх.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \makecell{\textbf{Необходими} \\ \textbf{подзадачи}} & $n$ & \textbf{Други ограничения} \\
        \hline
        	$0$ & $ 0$ & $-$ & $-$ & Примерните тестове.\\ 
        \hline
        	$1$ & $ 5$ & $-$ & $-$ & Всеки връх $u$ има ребро към най-много един друг.\\ 
		\hline
        	$2$ & $ 9$ & $1$ & $-$ & Всяка компонента има два върха с по едно ребро и всички останали върхове в компонентата имат по две ребра.\\ 
		\hline
        	$3$ & $16$ & $1,2$ & $-$ & Всеки връх $u$ има ребра към най-много два други.\\ 
		\hline
        	$4$ & $ 6$ & $1$ & $-$ & Всеки връх $u$ или има единствен съсед, или е единственият съсед на всички свои съседни върхове. \\ 
		\hline
			$5$ & $11$ & $-$ & $\le 1000$ & За всяка компонента е вярно, че броят на върховете в нея е с едно по-голям от броят на ребрата, които ги свързват. \\ 
		\hline
			$6$ & $15$ & $1,2,4$ & $-$ & За всяка компонента е вярно, че броят на върховете в нея е с едно по-голям от броят на ребрата, които ги свързват. \\ 
		\hline
			$7$ & $16$ & $0,5$ & $\le 1000$ & Няма. \\ 
		\hline
			$8$ & $22$ & $0-7$ & $-$ & Няма. \\ 
		\hline
    \end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}

\pagebreak

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|X[4,l]|X[1,l]|X[5,j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{8 7\\1 1 10 1 1 10 10 1 \\3 4\\3 2\\3 5\\7 1\\1 6\\6 8\\8 7} & 
		\texttt{30} & 
		{На следната графика виждате най-доброто възможно оценяване: \\ \includegraphics[width=0.3\textwidth]{graph_2.png}}\\
		\hline
	\end{tblr}
\end{table}

\end{document}

