SPOJ Brasil

Como parte do treinamento para as Olimpíadas do Rio 2016, uma equipe de atletas brasileiros precisa passar um bom tempo na academia. Dependendo das condições físicas e do papel do atleta na equipe, cada um recebeu uma série de exercícios que devem ser feitos ao longo do dia, com duração variada. A única recomendação comum a todos é que devem fazer seus exercícios sem intervalo: podem entrar na academia quando quiserem, mas depois de entrar, devem fazer todos os exercícios sugeridos pelo treinador, e só então podem sair da academia; e depois de sair não voltam mais. O treinador está desconfiado que um de seus atletas é mentiroso e não está nem aí para o treinamento.

Certo dia perguntou a cada um dos atletas quem ele tinha visto na academia no dia anterior. Arthur disse que tinha visto Bruno e Cesar; Bruno afirma ter visto Arthur e Everton; Cesar disse que viu Bruno; Diego afirma ter visto Arthur e Everton; e Everton disse ter visto Cesar e Diego. A figura abaixo foi feita com essas informações: uma seta de X para Y indica que X afirma ter visto Y.

Sabe-se que enquanto um atleta está na academia, não vê necessariamente todos os que passam por lá durante esse tempo. Mas sempre que dois estiveram presentes na academia simultaneamente, mesmo que por pouco tempo, pelo menos um deles vê o outro. Por exemplo, pelas informações acima é possível concluir que Bruno e Diego não estiverem presentes simultaneamente em nenhum momento, pois nenhum deles viu o outro. Mas houve algum momento em que Arthur e Cesar estavam presentes simultaneamente, já que Arthur viu Cesar (isso é verdade mesmo Cesar não tendo visto Arthur).

Analisando as informações o treinador concluiu que Diego é o mentiroso.

Vejamos como: primeiramente vamos provar que entre Arthur, Bruno, Diego e Everton, um deles mentiu. Suponha, por um momento, que nenhum deles tenha mentido. Já vimos que Bruno e Diego não estiveram na academia simultaneamente, pois não se encontraram (Bruno não viu Diego nem Diego viu Bruno). Mas Arthur esteve com os dois. A figura abaixo mostra duas maneiras disso der ocorrido. Cada traço representa o horário em que o atleta esteve na academia.

Outras maneiras incluem Arthur chegando um pouco antes ou saindo um pouco depois, mas isso não interfere na conclusão a seguir. O fato é que Bruno e Diego estiverem com ele, mas em horários diferentes. Note que é impossível encaixar Everton nessa linha de tempo, pois pelos depoimentos, ele deve encontrar Bruno e Diego, e não encontrar Arthur.

O mesmo ocorre se montarmos uma linha de tempo com Arthur, Bruno e Everton (impossível encaixar Diego), ou com Arthur, Diego e Everton (impossível encaixar Bruno), ou com Bruno, Diego e Everton (impossível encaixar Arthur). Logo, é impossível que todos eles estejam falando a verdade.

Essa situação ocorre mesmo desconsiderando o depoimento de Arthur ou de Everton. Desconsiderando o depoimento de Bruno ocorre situação semelhante com Arthur, Cesar, Diego e Everton. Porém, desconsiderando o depoimento de Diego tudo se encaixa. Logo, Diego é o mentiroso.

O problema é que o número de atletas brasileiros classificados para as olimpíadas está crescendo e fica cada vez mais difícil descobrir o mentiroso. Use seu espírito olímpico para ajudar o treinador fazendo um programa que descobre o atleta mentiroso!

Entrada

Há vários casos de teste.

Cada caso de teste começa com um inteiro N, que representa o número de atletas (4 ≤ N ≤ 10). Em seguida há N linhas, descrevendo quem viu quem. A i-ésima linha começa com um inteiro Q_i, a quantidade de atletas que o i-ésimo atleta viu na academia (0 ≤ Q_i ≤ N-1), e em seguida, Q_i inteiros distintos, indicando quais são esses atletas. Os atletas são numerados de 1 a N. O primeiro caso de teste do exemplo a seguir é o do enunciado.

A entrada termina com N = 0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo o número do atleta mentiroso (haverá no máximo um atleta mentiroso em cada caso de teste, e se houver será possível identificá-lo pelos depoimentos). Ou então a frase “nenhum mentiroso” caso os depoimentos sejam coerentes e nenhum mentiroso possa ser identificado a partir deles.

Exemplos

Entrada:
5
2 2 3
2 1 5
1 2
2 1 5
2 3 4
6
2 2 5
2 3 5
2 2 4
1 5
2 3 6
1 1
6
2 2 4
2 1 6
2 5 6
2 2 3
2 1 6
2 3 4
0

Saída:
4
nenhum mentiroso
5