92 lines
3.0 KiB
TeX
92 lines
3.0 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{Metro}{1}{256}{OBI 2015}
|
|
|
|
As cidades da Cosmolândia usam sistemas de metrô com uma organização muito
|
|
regular. Existe uma estação central, várias linhas radiais saindo dela, e uma
|
|
linha circular que passa ao redor da estação central.
|
|
|
|
Cada linha radial começa na estação central, segue sem cruzar as outras linhas
|
|
radiais e encontra a linha circular em alguma estação. Depois desse encontro,
|
|
ela ainda pode continuar até regiões mais afastadas da cidade.
|
|
|
|
O sistema possui $N$ estações, numeradas de $1$ a $N$. Esses números não indicam
|
|
a posição das estações. Você recebe apenas a lista de ligações diretas entre
|
|
pares de estações e deve determinar por quantas estações passa a linha circular.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\includegraphics[width=0.7\textwidth]{image.png}
|
|
\caption{Exemplo de um sistema de metrô da Cosmolândia.}
|
|
\end{figure}
|
|
|
|
\Entrada
|
|
|
|
A primeira linha contém dois inteiros $N$ e $M$ ($6 \le N \le 20000$,
|
|
$0 \le M \le 20100$), indicando respectivamente o número de estações e o número
|
|
de ligações diretas entre pares de estações.
|
|
|
|
Cada uma das próximas $M$ linhas contém dois inteiros $P$ e $Q$
|
|
($1 \le P, Q \le N$, $P \ne Q$), indicando que existe uma ligação direta entre
|
|
as estações $P$ e $Q$.
|
|
|
|
É garantido que o sistema descrito segue o padrão de metrô da Cosmolândia:
|
|
existe uma única estação central, dela saem pelo menos $5$ e no máximo $100$
|
|
linhas radiais, e há no máximo uma ligação direta entre qualquer par de
|
|
estações.
|
|
|
|
\Saida
|
|
|
|
Imprima um único inteiro: o número de estações pelas quais passa a linha
|
|
circular do sistema de metrô.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{6~10} & \texttt{5}\\
|
|
\texttt{1~6} & \\
|
|
\texttt{1~3} & \\
|
|
\texttt{4~1} & \\
|
|
\texttt{3~4} & \\
|
|
\texttt{5~4} & \\
|
|
\texttt{3~5} & \\
|
|
\texttt{2~5} & \\
|
|
\texttt{3~2} & \\
|
|
\texttt{6~3} & \\
|
|
\texttt{2~6} & \\
|
|
\rowcolor{gray!20}\texttt{12~17} & \texttt{8}\\
|
|
\rowcolor{gray!20}\texttt{7~1} & \\
|
|
\rowcolor{gray!20}\texttt{9~3} & \\
|
|
\rowcolor{gray!20}\texttt{5~1} & \\
|
|
\rowcolor{gray!20}\texttt{7~12} & \\
|
|
\rowcolor{gray!20}\texttt{7~3} & \\
|
|
\rowcolor{gray!20}\texttt{4~10} & \\
|
|
\rowcolor{gray!20}\texttt{3~2} & \\
|
|
\rowcolor{gray!20}\texttt{6~8} & \\
|
|
\rowcolor{gray!20}\texttt{10~5} & \\
|
|
\rowcolor{gray!20}\texttt{7~6} & \\
|
|
\rowcolor{gray!20}\texttt{2~11} & \\
|
|
\rowcolor{gray!20}\texttt{7~10} & \\
|
|
\rowcolor{gray!20}\texttt{12~4} & \\
|
|
\rowcolor{gray!20}\texttt{8~9} & \\
|
|
\rowcolor{gray!20}\texttt{3~12} & \\
|
|
\rowcolor{gray!20}\texttt{1~8} & \\
|
|
\rowcolor{gray!20}\texttt{7~4} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
No primeiro exemplo, a estação central é a estação $3$. Ao remover essa estação
|
|
e as partes radiais que não pertencem ao círculo, sobram as estações
|
|
$1, 6, 2, 5$ e $4$, portanto a linha circular passa por $5$ estações.
|
|
|
|
No segundo exemplo, aplicar o mesmo processo deixa $8$ estações na linha
|
|
circular.
|
|
|
|
Problema adaptado da OBI 2015, Fase 1:
|
|
\href{https://olimpiada.ic.unicamp.br/pratique/ps/2015/f1/metro/}{Metrô}.
|
|
\end{ProblemaAutor}
|
|
\end{document}
|