Avançado Informática - Semana 31

0 Flares Facebook 0 0 Flares ×

Imperialismo

 

A ambição de conquista e expansão é uma doença muito conhecida no planeta Terra... E também em todo o universo.

No planeta "Imperius" várias fortalezas foram construídas uma de cada vez e cada uma delas, menos a primeira, estavam ligadas no momento da sua construção para uma fortaleza previamente construída por um caminho direto, para fins comerciais.

Imperius estava se tornando um dos planetas mais pacífico e próspero no universo, até que eles pararam de construir mais fortalezas. Naquele momento, surgiram N diferentes impérios (numeradas de 1 a N), cada um deles dominando uma fortaleza diferente. E a sede de conquista se apoderou de Imperius. Assim, a cada ano, exatamente um dos impérios vivos conquista cada império vizinho, e domina cada fortaleza pertencente a eles. Dois impérios são considerados vizinhos se existem duas fortalezas unidas por um caminho, cada uma dominada por um império diferente destes dois.

Eventualmente um único império vai dominar cada fortaleza. Sua tarefa é encontrar o número mínimo de anos que isso pode acontecer.

Como um exemplo, no lado esquerdo da figura abaixo um cenário possível é mostrado, onde seis fortalezas são inicialmente dominadas por seis impérios diferentes. Cada fortaleza é identificada com o número do império que a domina. Se o império 2 conquistou cada vizinho no primeiro ano, a situação seria como na figura central. Finalmente, se o império 5 conquistou seus impérios vizinhos, ele acabaria dominando cada fortaleza, como pode ser visto no lado direito da figura.

Entrada

A entrada contém vários casos de teste. Cada teste é descrito em duas linhas. A primeira linha contém um inteiro N (2 <= N <= 104) representando o número de fortalezas no planeta Imperius. A linha seguinte contémN-1 inteiros P_i indicando que a fortaleza i + 1 foi ligada a fortaleza P_i (1 <= P_i <= i para 1 <= i <= N-1). A última linha da entrada contém um único -1 e não deve ser processado como um caso de teste.

Saída

Para cada caso, imprima a saída em uma única linha com um número inteiro representando o número mínimo de anos de modo que um único império possa dominar todas as fortalezas.

Exemplo de Entrada Exemplo de Saída
6
1 2 2 4 5
7
1 1 3 3 4 4
6
1 2 2 2 2
-1
2
2
1
0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: