Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CARTOG11 - Desafio cartográfico

 

Leonardo Nascimento é um garoto de 13 anos apaixonado por cartografia. Ele assina a lista de discussões da Sociedade Brasileira de Cartografia (SBC) para ficar por dentro de todas as novidades. Em um tópico de discussão na lista da SBC, o presidente da sociedade descobriu que Leonardo tinha apenas 13 anos, e ficou muito feliz em saber que uma pessoa tão jovem tinha tanto interesse pela arte de traçar mapas geográficos e topográficos. Foi então que o presidente resolveu criar desafios com intuito de difundir a cartografia.

Um dos desafios era o seguinte: dado um mapa de cidades ligadas por estradas, determinar a distância entre um par de cidades mais distantes. Como o objetivo era fazer as crianças se divertirem, o presidente resolveu selecionar mapas bem simples. As restrições adotadas foram: (a) todas as estradas são de mão dupla; (b) todas as estradas possuem 1km de comprimento, e portanto toda estrada ligando duas cidades tem o mesmo comprimento; (c) toda estrada conecta apenas duas cidades, e (d) dadas duas cidades quaisquer A e B, só existe uma única maneira de chegar em A partindo de B, e vice-versa.

O presidente da SBC resolveu pedir sua ajuda para escrever um programa de computador que, dado um mapa seguindo as restrições acima, devolva a resposta. Assim, ele conseguirá gerar um gabarito para enviar junto com o desafio.

Entrada

A primeira linha da entrada contém um inteiro N representando o número de cidades no mapa. Cada uma das N−1 linhas seguintes da entrada contém dois inteiros A e B indicando que existe uma estrada entre as cidades A e B.

Saída

A única linha da saída contém um inteiro indicando a distância entre um par de cidades mais distantes.

Restrições

  • 2 ≤ N ≤ 106
  • 1 ≤ A, BN e AB

Exemplos

Entrada
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Saída
9

Entrada
5
1 2
2 3
3 4
3 5

Saída
3

A figura abaixo ilustra este exemplo, onde temos 5 cidades identificadas por 1, 2, . . . , 5. As cidades 1 e 4 estão a uma distância de 3km, assim como as cidades 1 e 5. Não temos nenhum par de cidades que estão a uma distância maior que 3km. Portanto, a resposta para esse caso é 3.


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
Tempo limite:0.162s-0.983s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 1 nível 2

hide comments
2014-05-31 17:36:52 Leonardo Ferreira [UFES]
oi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.