% Idee: Atcoder https://atcoder.jp/contests/abc160/tasks/abc160_d, Andres Alumets
% Tekst: Andres Alumets

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}

\usepackage{tikz}
\usetikzlibrary{calc}

\begin{document}
\begin{ol}{\eio}{\ev 4.12.2025}{\yle}{}
    \begin{yl}{6}{Mugandatud ahel}{ahel}{1 sek / 3 sek}{100 punkti}
        Sul on $N$ tipuga suunamata graaf. Graafi tipud on nummerdatud $1$ kuni $N$. Graafi servad on konstrueeritud järgnevalt:
        \begin{xitem}
            \item Iga arvu $i \in \{1, 2, \ldots, N-1\}$ kohta on serv tippude $i$ ja $i+1$ vahel.
            \item Samuti on serv tippude $X$ ja $Y$ vahel.
            \item Rohkem servi graafis pole.
            \item Iga serva pikkus on $1$ ühik.
        \end{xitem}

        Nüüd pead leidma iga arvu $k \in \{1, 2, \ldots, N-1\}$ kohta, mitu sellist tipupaari $(i, j)$ leidub, et $1 \le i < j \le N$ ning lühima tippude $i$ ja $j$ vahelise tee pikkus on $k$ ühikut.

        \sis Sisendi esimesel real on kolm täisarvu $N$, $X$ ja $Y$ ($3 \le N \le 10^5$, $1 \le X, Y \le N$, $|X-Y| \ge 2$).

        \val Väljastada $N-1$ rida, tipupaaride arvud vastavalt $k = 1, 2, \ldots, N-1$ puhul.

        \begin{wrapfigure}[1]{r}{0.4\textwidth}
          \begin{tikzpicture}[every node/.style={circle, draw, minimum size=20}]
            \foreach \i in {1,...,5} \draw (1.4 * \i, 0) node (\i) {\i};
            \foreach \i in {1,...,4} { \pgfmathtruncatemacro{\j}{\i+1}; \draw (\i) -- (\j); }
            \draw (2) to[out=45, in=135] (4);
          \end{tikzpicture}
        \end{wrapfigure}

        \nde[0]{3cm}{3cm}

        Paarid kaugusega $1$ on $(1, 2)$, $(2, 3)$, $(2, 4)$, $(3, 4)$, $(4, 5)$.

        Paarid kaugusega $2$ on $(1, 3)$, $(1, 4)$, $(2, 5)$, $(3, 5)$.

        Paar kaugusega $3$ on $(1, 5)$.

        Paare kaugusega $4$ ei ole.

        \nde[1]{3cm}{3cm}

        \nde[2]{3cm}{3cm}

        \nde[3]{3cm}{3cm}

        \clearpage
        \hnd \testidgrupis
        \begin{xenum0}
            \item (0 punkti) \naitedlyhem
            \item (25 punkti) $N \le 100$.
            \item (25 punkti) $N \le 5\,000$.
            \item (50 punkti) \piiranguteta
        \end{xenum0}

        \malulimiit{1~GB}
    \end{yl}
\end{ol}
\end{document}
