Essa é pros feras! (Desafio de programação)

Há um tempo atrás passava o tempo resolvendo problemas como este, se vcs se interessarem, eu posto mais...

[size=24:152145d54f]Árvores[/size:152145d54f]

Como todos vocês devem ter percebido durante o curso, árvores são fundamentais em vários ramos (!) da Computação. Este problema envolve a construção e percurso de árvores binárias.

[size=24:152145d54f]Tarefa[/size:152145d54f]

Dada uma árvore binária, você deve escrever um programa que produza um percurso ´em níveis´. Cada vértice de uma árvore contém um inteiro positivo que identifica o vértice unicamente. Em um percurso em níveis os vértices em um dado nível são visitados da esquerda para a direita, e todos os nós do nível k são visitados antes dos nós do nível k + 1. Por exemplo, para a árvore abaixo,
[img:152145d54f]http://www.afw.hpg.com.br/Contestos/ProvaOBI2000-Fase2-3.gif[/img:152145d54f]
um percurso em nível produz 5, 4, 8, 11, 13, 4, 7, 2, 1.

[size=24:152145d54f]Entrada[/size:152145d54f]

Na entrada uma árvore binária é especificada como uma seqüência de pares (v, p) onde v é o valor do vértice cujo caminho desde a raiz é descrito pelo vetor p. Os elementos de p têm valor 1 ou -1, representanto respectivamente um ramo direito ou um ramo esquerdo. O final do vetor p é indicado por um elemento de valor 0. Na árvore da figura acima, o vértice que contém 13 é especificado por (13, [1, -1, 0]) e o nó que contém 2 é especificado por (2, [-1, -1, 1, 0]). A raiz é especificada por (5, [0]), onde o vetor vazio representa o caminho da raiz até a própria raiz.
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro positivo N que indica o total de vértices da árvore. As N linhas seguintes contêm cada uma a descriçào de um vértice, no formato descrito acima. O final da entrada é indicado quando N = 0.

[size=24:152145d54f]Exemplo de Entrada[/size:152145d54f]
9
11 -1 -1 0
7 -1 -1 -1 0
8 1 0
5 0
4 -1 0
13 1 -1 0
2 -1 -1 1 0
1 1 1 1 0
4 1 1 0
3
10 0
20 -1 0
30 1 0
0

[size=24:152145d54f]Saída[/size:152145d54f]
Para cada conjunto de teste da entrada seu programa deve produzir três linhas. A primeira linha identifica o conjunto de teste, no formato ´Teste n´, onde n é numerado a partir de 1. A segunda linha deve conter os valores dos vértices na ordem do percurso em nível, conforme determinado pelo seu programa.
A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

[size=24:152145d54f]Exemplo de Saída[/size:152145d54f]


Teste 1
5 4 8 11 13 4 7 2 1

Teste 2
10 20 30

(esta saída corresponde ao exemplo de entrada acima)

[size=24:152145d54f]Restrições[/size:152145d54f]

0 ≤ N &8804; 10000 (N = 0 apenas para indicar o fim da
entrada)
0 &8804; valor de um vértice &8804; 10000

Dica: Observem uma propriedade das ávores binárias.