SPOJ Brasil

Asdrúbal é um caixeiro viajante (essa profissão é antiga, e designa uma pessoa que trabalha com vendas e percorre as cidades atendendo clientes).

Asdrúbal viaja somente de trem; sempre parte da cidade onde mora e retorna, ao final da viagem, para a mesma cidade. A sua empresa lhe forneceu um passe transporte que lhe permite viajar por toda a malha ferroviária, mas com algumas restrições importantes: ele deve retornar exatamente pelo mesmo caminho tomado na viagem de ida, e assim passa duas vezes em cada cidade (uma na ida e outra na volta), exceto na cidade em que ele inicia o trajeto de retorno (a ultima do trajeto de ida). A malha ferroviária é construída de tal forma que entre qualquer par de cidades existe apenas um trajeto possível, e a partir de uma cidade é possível viajar para qualquer outra cidade.

Sua empresa trabalha com turismo, e para maximizar seu lucro Asdrúbal precisa aproveitar as festas típicas que acontecem nas cidades para visitar os seus clientes. A empresa forneceu a Asdrúbal uma lista com a seqüência em que as festas típicas irão acontecer nas cidades. As festas típicas nunca são coincidentes, ou seja, todas acontecem em dias disjuntos. Além do mais, os trens são muito rápidos, de forma que Asdrúbal sempre consegue ir de uma cidade a qualquer outra da malha durante uma noite. Assim, ao partir de uma cidade no final do dia ele certamente conseguirá chegar à cidade que tem a próxima festa típica na manhã do dia seguinte.

Tarefa

Dada a descrição da malha ferroviária (cidades e ligações ferroviárias) e uma seqüência de cidades na ordem em que suas festas típicas acontecem, você deve escrever um programa para determinar qual o maior número de festas típicas a que Asdrúbal pode comparecer.

Entrada

A entrada é composta de vários conjuntos de testes. A primeira linha de um conjunto de testes contém dois inteiros C e F, separados por um espaço em branco, que indicam respectivamente o número de cidades na malha ferroviária (1 <= C <= 300) e número de festas típicas (1 <= F < 600). As cidades são identificadas por inteiros entre 1 e C; a cidade em que Asdrúbal reside é sempre identificada pelo número 1. Cada uma das C − 1 linhas seguintes contém dois inteiros X e Y, separados por um espaço em branco, indicando que há uma ligação ferroviária direta, sem passar por outra cidade, entre a cidade X e a cidade Y (1 <= X <= C, 1 <= Y <= C e X != Y). Note que uma ligação entre X e Y permite o trajeto de X para Y e de Y para X. A ultima linha de um conjunto de testes contém uma seqüência de F inteiros, separados por espaço em branco, indicando as cidades que possuem festas típicas, na ordem em que estas acontecem. O final da entrada é indicado por C = F = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n ́é numerado seqüencialmente a partir de 1. A segunda linha deve conter um número inteiro indicando o número máximo de festas típicas a que Asdrúbal pode comparecer. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Entrada:
4 4
2 3
4 2
2 1
2 4 3 1
5 6
1 2
1 3
1 4
1 5
1 2 3 4 5 1
0 0

Saída:
Teste 1
3

Teste 2
3

1 <= C <= 300 (C = 0 para indicar final da entrada)
1 <= F < 600 (F = 0 para indicar o final da entrada)
1 <= X <= C
1 <= Y <= C
X != Y