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

PASSEIO - Passeio de bicicleta

Em 2001, Arnaldinho foi um dos alunos que representou o seu país na Olimpíada Internacional de Informática (IOI), que ocorreu na cidade de Tampere, na Finlândia. Além de participar da IOI, Arnaldinho queria aproveitar a oportunidade para conhecer aquela cidade. Ao chegar em Tampere, Arnaldinho surpreendeu-se com um fato que talvez poucos saibam: na Finlândia, a bicicleta é o meio de transporte mais utilizado (no verão; no inverno, com temperaturas de até -30°, é impossível andar de bicicleta sem congelar). A IOI estava acontecendo no verão do hemisfério norte e Arnaldinho, que adora andar de bicicleta, decidiu alugar uma para fazer um passeio pelos principais pontos turísticos de Tampere.

Por azar de Arnaldinho, quando ele chegou ao primeiro dos pontos turísticos que ele foi visitar, a correia da bicicleta quebrou. Enquanto visitava este ponto turístico, Arnaldinho decidiu que continuaria o seu passeio mesmo com a correia da bicicleta quebrada, valendo-se das elevações da cidade. Arnaldinho então pegou um mapa com os pontos turísticos de Tampere e as ligações que os conectam. Para felicidade de Arnaldinho, como muitas pessoas passeiam por Tampere de bicicleta, o mapa trazia a altitude dos locais onde se situam todos os pontos turísticos. Além disto, o mapa mencionava que em Tampere, se um ponto turístico A está localizado em um local com altitude maior do que um outro ponto B, e existe ligação direta de A para B, então todo o percurso ao longo desta ligação é em descida. Arnaldinho quer visitar o maior número possível de pontos turísticos sendo que, como a sua bicicleta está estragada, depois de visitar um ponto turístico A ele só pode ir para outro ponto B que tenha altitude menor que A. Além disto, a Finlândia é um país muito civilizado, e Arnaldinho deve respeitar o sentido das ligações entre os pontos turísticos de Tampere.

Tarefa

A tua tarefa é ajudar Arnaldinho a encontrar, a partir do mapa com os pontos turísticos de Tampere e as ligações entre estes pontos, o número máximo de pontos turísticos que ele pode visitar, dado o ponto onde ele se encontra e a restrição de que, a partir de um ponto, ele só pode ir para outro com menor altitude.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém três números inteiros P, L e I, correspondendo, respectivamente, ao número de pontos turísticos, o número de ligações entre eles, e o número do ponto turístico onde Arnaldinho se encontra inicialmente. Os pontos turísticos são numerados seqüencialmente de 1 até P. A segunda linha contém P números inteiros, correspondendo às altitudes, em metros, dos locais onde se encontram os pontos turísticos de 1 a P, respectivamente. Cada uma das L linhas seguintes contém dois inteiros A e B, indicando que há uma ligação direta partindo do ponto turístico A até o ponto B. O final da entrada é indicado por um conjunto de teste com P = L = I = 0.

Saída

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 o número máximo de pontos turísticos que Arnaldinho ainda pode visitar (sem contar o ponto turístico onde ele está inicialmente). A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplos

Entrada:
4 7 2
100 150 50 200
1 2
2 1
2 4
4 3
4 2
3 2
3 1
4 7 4
100 50 150 200
1 2
2 1
2 4
4 3
4 2
3 2
3 1
0 0 0

Saída:
Teste 1
1

Teste 2
3

Restrições

0 ≤ P ≤ 150 (P = 0 apenas para indicar o fim da entrada)
0 ≤ L ≤ P*(P-1) (L = 0 apenas para indicar o fim da entrada)
0 ≤ I ≤ P (I = 0 apenas para indicar o fim da entrada)
0 ≤ H ≤ 1000 (altura dos pontos turísticos)
1 ≤ A ≤ P
1 ≤ B ≤ P
A ≠ B


Adicionado por:Wanderley Guimarăes
Data:2006-04-29
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2002 - Seletiva

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.