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

NOME - Dando nome aos times

O grande coach de maratona Da Silva percebeu que um dos maiores problemas para os times que competem é a escolha do nome. Os times perdem muito tempo pensando em um bom nome e esquecem de treinar. Para resolver esse problema Da Silva resolveu que ele próprio escolheria os nomes dos times. No entanto, para evitar uma revolta ele pretende considerar (um pouco) a opinião de cada time.

Da Silva propôs N nomes para os N times e pediu que cada um fizesse uma lista de preferência, ordenando os nomes de acordo com suas preferências. É claro que para cada nome Da Silva já tinha sua lista de preferência dos times a receber o nome.

A escolha dos nomes será feita de forma que no final não exista um time t1 com nome n1 e um time t2 com nome n2, sendo que t1 preferia o nome n2 ao n1 e Da Silva preferia dar o nome n2 para t1 ao invés de t2. Caso exista mais de uma possibilidade satisfazendo esse critério, será escolhida a que melhor segue a lista de preferência de Da Silva.

Sendo um coach muito ocupado, com viagens pelo mundo, Da Silva quer que você escreva um programa para a escolha dos nomes dos times.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

A primeira linha de cada instância contém um inteiro N indicando o número de times. Os times são identificados por números de 1 a N.

Cada uma das próximas N linhas possui um nome de time proposto por Da Silva, um espaço e a lista de preferência de Da Silva para o nome. A lista de preferência para um nome é dada por uma permutação de 1,...,N representando os times, com um espaço entre cada número, sendo o time mais a esquerda o de maior preferência.

Cada uma das N linhas seguintes possui a lista de preferência de cada time. A i-ésima dessas N linhas corresponde à lista do timei. A lista de preferência da cada time consiste nos N nomes de times ordenados de acordo com a preferência e separados por um espaço.

Restrições

1 <= N <= 300
Um nome de time não tem mais que 15 caracteres e não contém espaços.

Saída

Para cada instância imprima N linhas, sendo que a i-ésima linha deve conter apenas o nome de time que Da Silva escolherá para o time i.

Imprima uma linha em branco após a saída de cada instância.

Exemplo de entrada

2
2
cai_cai_balao 1 2
code_rupper 1 2
cai_cai_balao code_rupper
code_rupper cai_cai_balao
3
2towers.bin 1 2 3
cai_cai_balao 2 3 1
code_rupper 3 1 2
cai_cai_balao code_rupper 2towers.bin
code_rupper cai_cai_balao 2towers.bin
2towers.bin code_rupper cai_cai_balao

Saída para o exemplo de entrada

cai_cai_balao
code_rupper

2towers.bin
cai_cai_balao
code_rupper

Comentários

Na segunda instância do exemplo existem 3 soluções possíveis:

M1 = {(1, 2towers.bin), (2, cai_cai_balao), (3, code_rupper)}
M2 = {(1, cai_cai_balao), (2, code_rupper), (3, 2towers.bin)}
M3 = {(1, code_rupper), (2, cai_cai_balao), (3, 2towers.bin)}

M1 foi a escolhida, pois entre as 3 é a que melhor segue as preferências do coach.


Adicionado por:Wanderley Guimarăes
Data:2009-08-31
Tempo limite:0.569s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Segunda Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2011-09-30 20:44:10 Fernando Fonseca [ITA]
Tá meio aberto mesmo, vou tentar formalizar o que eu supus: uma soluçăo S é a que "segue melhor a preferęncia de Da Silva" se năo existe uma soluçăo T tal que, para todos os nomes, ou os nomes estejam com o mesmo time que em S ou com um time para o qual Da Silva preferiria dar o nome.
2010-08-01 17:07:27 Gabriel Luís Mello Dalalio [ITA]
Acho que o enunciado năo explicou direito o que fazer quando há mais de uma possibilidade, o que é exatamente seguir melhor a lista de preferęncia de Da Silva?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.