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

PRUFERMG - Sequência de Prüfer

Árvores são estruturas de fundamental importância em diversas áreas como teoria dos grafos e otimização combinatória, e podem ser empregadas para modelar soluções de muitos problemas do mundo real. Em algumas situações, é desejável obter uma representação compacta para a topologia de uma árvore, com o objetivo de reduzir o esforço computacional para processá-la.

Uma das representações comumente utilizadas é a sequência de Prüfer. Dada uma árvore rotulada com n vértices, a sequência de Prüfer que a representa univocamente tem tamanho n-2 e pode ser gerada de maneira muito simples por meio de um algoritmo iterativo, que remove vértices da árvore até que restem apenas dois vértices. Mais especificamente, considere uma árvore T com n vértices, com rótulos {1,2,...,n}. Na i-ésima iteração do algoritmo (1 ≤ i ≤ n-2), considere que vi denota o vértice folha com o menor rótulo em T. Atribua ao i-ésimo elemento da sequência de Prüfer o rótulo do único vértice adjacente a vi e remova vi de T. Ao final do algoritmo, a sequência de Prüfer terá tamanho n-2 e representará de maneira única a árvore rotulada T.

A sua tarefa é bem simples: determinar o grau de cada vértice da árvore representada por uma sequência de Prüfer.

Entrada

Há vários casos de teste.

Cada caso de teste é descrito em uma única linha, contendo inteiros separados por espaços em branco. O primeiro inteiro é o valor de K (1 ≤ K ≤ 1.048.576), que descreve o tamanho da sequência de Prüfer. Em seguida existem K inteiros si (1 ≤ si ≤ K + 2, \quad 1 ≤ i ≤ K), que descrevem a sequência de Prüfer.

A entrada termina com K=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma única linha contendo uma sequência de K+2 inteiros gi, em que gi indica o grau do vértice de rótulo i da árvore representada pela sequência de Prüfer.

Exemplos

Entrada:
4 4 4 4 5
0

Saída:
1 1 1 4 2 1

Adicionado por:Wanderley Guimarăes
Data:2014-05-09
Tempo limite:2s
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:Maratona Mineira 2013

hide comments
2014-05-19 22:17:04 oldenhero
1000 submissions later...
2014-05-16 05:21:00 Junior Andrade [UNIFEI]
Entrada acaba com EOF....

Last edit: 2014-05-16 19:37:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.