beecrowd | 2124

Mrs. Montagny Menu!

By XI Maratona de Programação IME-USP, 2007 AD Andorra

Timelimit: 1

Mrs. Montagny is a socialite of Quebec, who spends his holidays in Banff, in his mansion on the edge of Lake Louise. Their dinners are famous because she spends a questionnaire in advance to guests where they participate in the choice of menu. In the questionnaire, the famous magnate list all the dishes that you can make for dinner, offering a guest column to select the platter and another to veto it.

And allowed to make only two choices in the questionnaire, each guest can select a dish and another veto, veto two dishes or select two dishes. Mrs. Montagny ensures that all guests will have at least one of their wishes granted.

Previously she herself realized assembling the menu and meet its promise, but with the growth of your parties this has become impossible. So, she decided to hire you to do a program that receives requests from guests and answer if she can mount a menu for the party.


The entry consists of several cases. Each case starts with an integer N ( 1 ≤ N ≤ 1000), indicating the number of questionnaires received by Mrs. Montagny. Each of the next N lines contains two food names indicating the preference of each guest. A name of food is a sequence of letters [a-z] over a maximum of 20 letters. When the name of a food starts with ''!'' means that the guest want to veto the food, otherwise he wishes to select.


For each case, you should print a identifier "Instancia K", where K is the number of the current case. In the next line you should print "yes" if she can attend at least one desire of every guest and "no" otherwise. After each case, your program should print a blank line.

Sample Input Sample Output

!feijoada !file
rabada feijoada
arroz churrasco
!arroz !churrasco
arroz !churrasco
!arroz churrasco

Instancia 1

Instancia 2