O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto de dados contém duas linhas: a primeira linha contém o número de elementos a serem inseridos e a segunda linha contém os elementos que serão inseridos, na ordem em que aparecem, na árvore binária de busca (valores menores à esquerda e maiores à direita). Os exemplos de entrada representam as seguintes árvores:

    

Os conjuntos devem ser processados até o fim do arquivo.

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

O arquivo de saída contém, para cada entrada, o número do conjunto, seguido de duas linhas. A primeira indica o elemento mais alto do caminho (raiz da sub-árvore) e o comprimento do caminho. Na segunda, os nós deste caminho devem sem impressos em in-ordem. Uma linha em branco deve ser impressa após cada conjunto.

Atenção: Lembre-se que o caminho de comprimento máximo entre descendentes de um vértice, não necessariamente passa por ele. Se existir mais de uma resposta, dê prefêrencia ao caminho que passe pelo vértice, se houver. Em caso de empate, dê prioridade aos filhos da esquerda.

A solução dos exemplos são mostrados a seguir:

    

Saída da entrada acima:

Conjunto #1
Raiz = 5 Comprimento = 4
1 2 5 7 8

Conjunto #2
Raiz = 4 Comprimento = 5
1 2 4 6 7 8

Obs.:

• Não se esqueçam de desalocar todos os nós (em JAVA, deixar de referenciar objetos não utilizados) da árvore entre cada processamento;
• Não serão inseridos valores iguais;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.

O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto começa com uma linha contendo o número N de vértices do grafo e o vértice de origem. As próximas N linhas de cada conjunto contêm as listas de adjacências do grafo. O primeiro número de cada uma das X linhas é um inteiro V (1 ≤ V ≤ N). Depois seguem vários pares de inteiros. Cada par possui um vértice W adjacente ao vértice V e o peso P da aresta (V,W). A lista de pares termina com um zero. O arquivo de entrada é terminado com o fim do arquivo. Considere que 1 ≤ N ≤ 500 e que cada vértice tem distância menor do que 1.000.000.

Atenção: A escolha do vértice de menor custo acumulado a cada iteração do algoritmo deve ser feita de maneira eficiente, utilizando um Heap.

7 1
1  2 2  3 5  4 3  0
2  1 2  5 6  0
3  1 5  5 3  6 4  0
4  1 3  6 8  0
5  2 6  3 3  7 6  0
6  3 4  4 8  7 5  0
7  5 6  6 5  0

Para cada conjunto, você deve imprimir N linhas. Na primeira linha, imprima o número do conjunto de dado, como mostrado na saída exemplo. Nas próximas N-1 linhas imprima um par V -> W: (onde W é um vértice do grafo), o custo do melhor caminho de V a W e a quantidade de caminhos com este custo para W. Imprima uma linha em branco após cada conjunto.

Conjunto #1
1 -> 2: Custo = 2 Caminhos = 1
1 -> 3: Custo = 5 Caminhos = 1
1 -> 4: Custo = 3 Caminhos = 1
1 -> 5: Custo = 8 Caminhos = 2
1 -> 6: Custo = 9 Caminhos = 1
1 -> 7: Custo = 14 Caminhos = 3

    

Obs.:

• Não se esqueçam de desalocar todos os nós (em JAVA, deixar de referenciar objetos não utilizados) da árvore entre cada processamento;
• Não serão inseridos valores iguais;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.