uCoder | 1193 | Nível: 5 | Tempo Limite: 5
Metrô
Adaptado por Erich Rodrigues
Competição: OBI 2015, Nível Universitário, Fase 1
Os sistemas de Metrô das cidades da Cosmolândia seguem sempre o mesmo padrão. Há uma estação central e uma linha circular, de modo que a estação central está dentro da área delimitada pela linha circular. A partir da estação central saem pelo menos 5, e no máximo 100, linhas radiais que não se interceptam entre si e que vão pelo menos até alguma estação da linha circular, podendo ir muito além, até os subúrbios mais remotos da cidade. Veja um exemplo na figura abaixo, que possui 6 linhas radiais e onde a linha circular passa por 16 estações.
Cada sistema possui N estações, numeradas de 1 a N . O número de uma estação não tem relação alguma com a sua posição no sistema. O problema é o seguinte. Um engenheiro da Agência Federal de Trânsito da Cosmolândia precisa descobrir rapidamente por quantas estações a linha circular passa. Ele tem apenas a informação sobre as ligações entre pares de estações, sem qualquer identificação das linhas às quais pertencem as duas estações do par. Você pode ajudá-lo?
Entrada
A primeira linha da entrada contém dois inteiros N e M , respectivamente, o número total de estações e de ligações entre pares de estações. As M linhas seguintes contêm, cada uma, dois inteiros P e Q, indicando que a estação de número P está ligada à estação de número Q.
Saída
Seu programa deve imprimir um inteiro, representando o número de estações pelas quais passa a linha circular do sistema.
Restrições
• 6 ≤ N ≤ 20000, M ≤ 20100
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
12 17 |
8 |
|
6 10 |
5 |