Problem
Uma das citações mais famosas do desenho animado: "Ohana — significa família, na família eles não vão deixar ninguém e nunca vão esquecer…» O que mais há para adicionar? Assim é!
Lilo quer fazer uma árvore genealógica de sua família para tentar encontrar o maior número possível de parentes. Na árvore genealógica, como você sabe, todos, exceto o ancestral, têm exatamente um dos pais. Lilo quer saber como posicionar dois membros da família um em relação ao outro. A irmã mais velha de Lilo, Nani, lembra perfeitamente quem é o pai de quem. Ela está pronta para ajudar Lilo, mas tem muito trabalho a fazer. Ajude a Nani a escrever um programa para o Lilo.
Entrada
O programa recebe como entrada o número de elementos da árvore genealógica N. Isso é seguido por uma string \(N-1\) que especifica o pai de cada elemento na árvore, exceto o ancestral. Cada linha se parece com:
child_name parent_name.
Mais ao final do arquivo existem linhas contendo os nomes de dois elementos da árvore.
Impressão
Para cada consulta, imprima um dos três números:
1 - se o primeiro elemento for um ancestral do segundo;
2 - se o segundo for ancestral do primeiro;
0 - se nenhum for ancestral do outro.
Exemplos
| # |
Entrada |
Saída |
| 1 |
9
Keaka Kayla
Ikika Kayla
Akeneki Kayla
Neolani Keaka
Ley Ikika
Kianalu Ley
Aalona Kianalu
Iukini Kianalu
Ikika Iukini
Neolani Kayla
Keaka Kianalu
FIM!
|
1 2 0
|