SPOJ Brasil

Sra. Montagny é uma socialite de Quebec, que passa as férias em Banff, na sua mansão à beira do Lake Louise. Seus jantares são famosos porque ela com antecedência passa um questionário aos convidados onde os mesmos participam da escolha do cardápio. No questionário, a famosa magnata lista todos os pratos que poderá fazer no jantar, oferecendo uma coluna para o convidado selecionar o prato e outra para vetá-lo. É permitido fazer apenas duas escolhas no questionário, ou seja, cada convidado pode selecionar um prato e vetar outro, vetar dois pratos ou selecionar dois pratos. A Sra. Montagny garante que todos os convidados terão pelo menos um de seus desejos atendidos.

Antigamente ela mesma dava conta de montar o cardápio e atender o que prometia, mas com o crescimento de suas festas isso tem se tornado impossível. Assim, ela resolveu contratar vocês para fazer um programa que recebe os pedidos dos convidados e responde se é montar um possível cardápio para a festa.

Entrada

A entrada é composta de diversas instâncias. Cada instância começa com um inteiro n (1 <= n <= 1000), indicando a quantidade de questionários recebidos pela Sra. Montagny. Cada uma das próximas n linhas contém dois nomes de comida indicando a preferência de cada convidado. Um nome de comida é uma seqüência de letras [a-z] com no máximo 20 letras. Quando o nome de uma comida é iniciado por "!" significa que o convidado deseja vetar a comida, caso contrário ele deseja selecionar.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte você deve imprimir sim se for possível atender pelo menos um desejo de cada convidado e nao caso contrário.

Após cada instância, seu programa deve imprimir uma linha em branco.

Exemplo

Entrada
2
!feijoada !file
rabada feijoada
4
arroz churrasco
!arroz !churrasco
arroz !churrasco
!arroz churrasco

Saída
Instancia 1
sim

Instancia 2
nao