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.|

GENEAL - Árvore Genealógica

A empresa Genesis faz vários serviços dedicados a famílias, principalmente para descobrir parentes e parentescos perdidos. Para mostrar a eficiência de seus serviços, a Genesis quer, para cada árvore genealógica que ela tem, achar o par de parentes com parentesco mais distante. Para isso, eles definiram uma "função-parentesco" definida da seguinte forma:

  1. grau(A, B) = 0, se A = B
  2. grau(A, B) = 1 + min{grau(pai(A), B), grau(A, pai(B))}, se A != B

Você deve fazer um programa que, dado uma árvore genealógica, imprime o nome dos dois parentes com maior grau de parentesco.

Entrada

A entrada é composta de um único caso de teste. A primeira linha contém um número inteiro positivo N, que indica o número de relações pai-filho que serão descritas. As N linhas seguintes contêm duas strings cada, P e F, indicando que P é pai de F.

Saída

Seu programa deve imprimir uma única linha contendo os nomes do par de parentes com maior grau de parentesco, e esse grau. Essas duas strings devem estar em ordem alfabética; em caso de empate, você pode imprimir qualquer par com essa característica.

Restrições

  • 2 ≤ N ≤ 1000
  • Todos os nomes tem tamanho máximo 50.

Exemplo

Entrada
11
arnaldo daniel
alfredo rafael
alfredo deborah
angela marcelo
julio arnaldo
angela elaine
angela guilherme
arnaldo renato
marcelo beatriz
julio angela
julio alfredo

Saída
beatriz daniel 5

Entrada
5
a b
b c
a d
d e
e f

Saída
c f 5


Adicionado por:Wanderley Guimarăes
Data:2009-01-27
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO OBJC PERL6 PY_NBC SCALA SQLITE TCL
Origem:Treino para OBI de 2006 - Fábio Moreira & Daniel Fleischman

hide comments
2016-04-23 06:32:13
Caro Elsio [UFABC] , conforme você mesmo já observou em outros problemas: Floyd-Warshall neles. Esquece esse negócio de pais, trate como arestas bidirecionais que dá certo.
2016-04-21 14:46:00 Elsio [UFABC]
Que acontece se não encontrarmos o pai de A ou o pai de B?
2015-04-11 18:17:47 Thalyson Nepomuceno [UECE]
fui confiando nessa linha em branco a mais... tomei 2 WA xD
parece q năo ta mais precisando disso.
2014-08-14 22:41:14 Alessandro Ferreira - UFMS
Como o Diego Buchinger [UDESC] disse, o enunciado está incorreto, a saída deve conter 2 linhas, uma com a resposta e uma em branco no final ( '\n' ).
2014-07-23 20:03:13 Tiago Nápoli
Ordem alfabética != ordem lexicográfica
2011-09-18 23:53:02 thiagojobson [UERN]
Se liguem tbm que o número de pessoas na árvore pode ser != N
mas respeitam o limite de 1000 :D

Last edit: 2011-09-19 00:06:47
2011-02-05 15:54:52 Diego Buchinger [UDESC]
Detalhe: as respostas devem ter no final um '\n' (thanks to unioeste)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.