% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
\renewcommand{\tl}{$0.5$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача T73. ВРЪЗКИ}
\addauthor{Автор: Иван Лупов (заета от РСОП 2024)}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	7 клас
}

За да не изостават с подготовката по информатика, докато госпожата по немски не внимава, Дамян и Калоян взимат един граф и решават да добавят $k$ нови ребра в него. Двамата обаче не могат да се съгласят какво искат да постигнат, добавяйки тези ребра в графа -- Калоян смята, че е по-добре графът да има минимален възможен брой свързани компоненти, а Дамян желае графът да има колкото се може повече свързани компоненти.

Вие нямате особени предпочитания по въпроса, но като техен мил приятел им предоставяте програма \texttt{\textbf{links}}, която пресмята колко е минималният брой и максималният брой компоненти, в резултат на някакво добавяне на \textit{точно} $k$ ребра в графа. Гарантирано е, че това винаги е възможно.

Графът е прост. Това означава, че:
\begin{itemize}
    \item Няма ребра, които са примки (между един и същ връх).
    \item Няма мултиребра (ребра между една и съща двойка върхове).
\end{itemize}

\subsection{Вход}
От първия ред на стандартния вход се въвеждат три числа $n$, $m$, $k$ -- броят върхове, броят ребра в началния граф и броят ребра, които ще се добавят. От следващите $m$ реда се въвежда по една двойка $u$, $v$, описваща едно ребро на графа.

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

\subsection{Ограничения и оценяване}
\begin{itemize}
	\item $2 \le n, m \le 10^5$
	\item $0 \le k \le \min \left(10^9, \frac{n(n - 1)}{2} - m\right)$
	\item В около $16\%$ от тестовете: $k = 0$.
	\item За всеки тест получавате $50\%$ от точките на теста за всяко правилно изведено число.
\end{itemize}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|l|l|}
		\hline
		\textbf{Вход 1} & \textbf{Изход 1} & \textbf{Вход 2} & \textbf{Изход 2}\\
		\hline
		\texttt{3 1 1\\1 2} & 
		\texttt{1 1} & 
		\texttt{6 2 3\\1 2\\3 4} & 
		\texttt{1 3}\\
		\hline
	\end{tblr}
\end{table}

\end{document}
