beecrowd | 2050

Ramsey's Saloon

By IX Maratona de Programação IME-USP, 2005 BR Brazil

Timelimit: 1

Bill "Snake" Ramsey was one of the most famous saloon owners in San Antonio. His saloon was known up to the West Coast, and his poker tables, which were always full, were also a synonym for electrifying games, lot's of money and, quite often, bloody quarrels.

Ramsey had a theory (and his .38 revolver intimidated those who disagreed with it) that at a poker table with 6 participants there would always be 3 who were friends with eachother, or 3 who were enemies between eachother (in those times in San Antonio if you weren't someones friend, he automatically became your enemy). Today we know that in fact Ramsey was right.

Your job in this problem is to check Ramsey's statement for various examples.


Multiple poker tables are given (each table always has 6 players). For each table the number M (-1 ≤ M ≤ 15) of pairs of friends is given, followed by, in the next line, the names of the participants of that game (each name is a string with at least 1 and at most 15 characters and you can suppose that the names of the players are pairwise distinct). After that, there are M lines, each one with names of two friends in that table. You should consider that a player is not a friend of himself. The value -1 indicates the end of the data.


For each instance solved, you must print an identifier Instancia h, in which h is an integer, sequential and crescent, starting from 1. On the following lines, you must print the names of three players in that table, followed by sao amigos (are friends) or sao inimigos (are enemies), according to the case. There must be as many lines as cases (relations) determined. These lines must be listed in lexographical order. The same must be true for the three names on any given line. A blank line must sepparate the output of each instance.

Sample Input Sample Output

jack john bill jesse james pil
jack john
jack bill
jack jesse
bill james
jesse james
james pil

Instancia 1
bill jesse john sao inimigos
bill jesse pil sao inimigos
bill john pil sao inimigos
jesse john pil sao inimigos