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

\begin{document}

\renewcommand{\tl}{$1.5$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача А1. БЕЛОТ}
\addauthor{Автор: Илиян Йорданов}{2025}{12}{20}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	Общински кръг, 20 декември 2025 г.\\
	Група A – 11, 12 клас
}

Никола и неговите приятели се събрали наскоро на олимпийска среща. По едно време започнало да се обсъжда главно това кой е по-добър на играта белот. Никола твърдял, че той е най-добър, но други оспорвали това. Общо имало $N$ приятели, които ще асоциираме с числата от $1$ до $N$. Те решили да проведат $M$ игри на белот през следващите $N$ дни, като във всяка игра ще участват точно двама от тях\footnote{Може да считате, че играят версията на белот за двама играчи, а не нормалната за четирима играчи.}. Ще представяме всяка игра като наредена двойка $(x_i, y_i)$, $1 \le x_i < y_i \le N$.

През ден $a$ ($1 \le a \le N$) приятел $a$ ще изиграе останалите игри, в които е включен (няма да се повтарят игри). Оказало се, че може да се наложи провеждането и на допълнителни игри. По-точно, ако в ден $a$, приятел $a$ участва в игра $(a, b)$, $a < b$, както и в игра $(a, c)$, $a < c, c \neq b$, то трябва да има и игра в някой от следващите дни с участието на приятели $b$ и $c$, за да се сравнят помежду си и те. Забележете, че не е задължително $(a, b)$ и $(a, c)$ да са от началните игри. Това може да направи общия брой игри доста голям, затова напишете програма \textbf{\texttt{belote}}, която намира този брой.

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

\subsection{Изход}
Отпечатайте едно самотно число равно на общия брой игри, които ще трябва да се изиграят.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \le N, M \le 100~000$
\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{Точки} & \textbf{Необходими подзадачи} & $N$ & \textbf{Други ограничения} \\
		\hline
		$0$ & $0$ & $-$ & $-$ & Примерът. \\ 
		\hline
		$1$ & $20$ & $0$ & $\le 100$ & -- \\ 
		\hline
		$2$ & $30$ & $0-1$ & $\le 3~500$ & -- \\
		\hline
		$3$ & $5$ & $0-2$ & $\leq 5~000$ & -- \\
		\hline
		$4$ & $10$ & $0-3$ & $\leq 50~000$ & -- \\
		\hline
		$5$ & $15$ & $-$ & $\leq 100~000$ & За всяко $1 \le k \le N$ има най-много една начална игра с $(x_i, y_i)$, за която $y_i = k$. \\
		\hline
		$6$ & $20$ & $0-5$ & $\leq 100~000$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\newpage
\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{
			9 8\\
			2 5\\
			2 6\\
			2 7\\
			1 2\\
			1 3\\
			4 8\\
			4 7\\
			7 8
		}}
		&
		\texttt{15}
		& 
		{Игрите по дни са следните, като редът в даден ден не е от значение:\\
			\tabitem ден $1$: $(1, 2)$, $(1, 3)$ (това предизвиква допълнителна игра между приятели $2$ и $3$)\\
			\tabitem ден $2$: $(2, 3)$, $(2, 5)$, $(2, 6)$, $(2, 7)$ (това предизвиква допълнителни игри между приятели $3$ и $5$, $3$ и $6$, $3$ и $7$, $5$ и $6$, $5$ и $7$, $6$ и $7$)\\
			\tabitem ден $3$: $(3, 5)$, $(3, 6)$, $(3, 7)$ (няма нови допълнителни игри, забележете че не се повтарят отново игрите между приятели $3$ и $1$, $3$ и $2$)\\
			\tabitem ден $4$: $(4, 7)$, $(4, 8)$ (няма нови допълнителни игри)\\
			\tabitem ден $5$: $(5, 6)$, $(5, 7)$ (няма нови допълнителни игри)\\
			\tabitem ден $6$: $(6, 7)$\\
			\tabitem ден $7$: $(7, 8)$\\
			\tabitem ден $8$: няма останали игри с приятел $8$\\
			\tabitem ден $9$: няма игри с приятел $9$.\\
		Допълнителните игри, които се изиграват са $(2, 3), (3, 5), (3, 6), (3, 7), (5, 6)$, $(5, 7)$ и $(6, 7)$. Забележете, че макар да имаме игрите с $(6, 7)$ и $(7, 8)$ това не предизвиква игра с $(6, 8)$, защото първата игра се изиграва през ден $6$, а втората игра през ден $7$.} \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier

\end{document}