Bessie e Farmer John visitam Mootreepolis, mas se separam e ela se perde. Um grupo a procura; só a direção do mugido, audível em toda a cidade, permite localizá-la.

O transporte é árvore, como o nome: $N$ locais ($1 \le N \le 100,000$), numerados $0$..$N$-$1$, unidos por $N$-$1$ caminhos bidirecionais, caminho único entre qualquer par. Bessie está num dos $N$ locais.

Há um buscador em cada um dos $N$ locais. FJ pode ligar para saber direção do mugido, qual caminho leva a Bessie, ou que ela está lá.

Telefone caro, quer minimizar ligações. Indique onde ligar, especialmente garantindo até $20$ antes de relatar a posição.

Nota: em $50\%$ das entradas $N$ é no máximo $1000$.

Leia primeiro o mapa da entrada padrão, depois interaja com avaliador pela entrada/saída padrão. Cada linha inicial lista caminhos de um local; índices da lista começam em zero para interação.

Primeira linha $N$, seguintes: vizinhos desde local $0$. Primeiro inteiro $K$ ($1 \le K \le N$), número de vizinhos, depois $K$ inteiros $N_{0}$, $N_{1}$, …, $N_{K-1}$, índices dos vizinhos desde zero. Um caminho define vizinhos.

Imprima locais em sequência. Cada resposta é índice do caminho rumo a Bessie na linha inicial correspondente. Leia da entrada padrão.

Imprimir o local dela termina automaticamente. No QOJ o avaliador fecha o fluxo de respostas quando a encontra; termine normalmente ao atingir fim de entrada lendo resposta.

Respostas podem ser adaptativas, mas todas compatíveis com ao menos uma localização possível.

Ao encontrá-la anuncia pontuação não nula: até $20$ consultas incluindo atual dá $10$, $30$ ou mais dá $0$, outras $30$ menos consultas feitas.

Suponha Bessie no nó $5$ do mapa, descrição de entrada à direita:

                               Node Count Neighbors
                0   1            0      1 3
                |   |            1      1 4
             2--3---4--5(B)      2      1 3
                |   |            3      4 0 2 6 4
                6   7            4      4 3 7 1 5
                                 5      1 4
                                 6      1 3
                                 7      1 4

Tabela de interação: query para saída padrão, response da entrada padrão, location local indicado. details é lista completa ordenada de vizinhos com interpretação em <>:

Query   Response    Location     Neighbor list details 
  2        0           3          <3>
  6        0           3          <3>
  3        3           4          0 2 6 <4>
  4        3           5          3 7 1 <5>
  5        Done; program will be terminated

De $2$, $6$, vizinho mais próximo e único $3$. De $3$, $4$; de $4$, $5$. Está em $5$, imprimir $5$ termina o programa.

Programas interativos

Esvazie a saída para dados não ficarem no buffer.

C/C++ com stdio.h, inclua:

setbuf(stdout, 0);

perto do início do programa.

C++ iostream, esvazie cada linha assim:

cout << line << "\n" << flush;

Pascal, após cada writeln, acrescente:

flush(stdout);

Java, após cada saída, acrescente:

System.out.flush();

Tempo excedido após resposta provavelmente significa saída não esvaziada corretamente.

Usuários de Java

Aqui (esperamos) o esqueleto de entrada/saída necessário:

import java.io.*;
import java.util.*;

public class cowtree {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new
                                          InputStreamReader(System.in));
        /* write ... */
        System.out.println(...);
        System.out.flush();

        /* read a reply */
        response = in.readLine();
        ...

Node: nó

Count: quantidade

Neighbors: vizinhos

Query: consulta

Response: resposta

Location: local

Neighbor list details: detalhes da lista de vizinhos

Done; program will be terminated: pronto, programa será encerrado

write ...: escrever

read a reply: ler resposta

Entrada

• Linha $1$: inteiro $N$.

• Linhas $2..N+1$: linha $i+2$ descreve vizinhos do local $i$ com inteiros separados $K$, $N_{0}$, …, $N_{K-1}$.

Saída

• Nenhuma linha em arquivo de saída: escreva na saída padrão, não no arquivo.

Exemplos

Entrada 1

8
1 3
1 4
1 3
4 0 2 6 4
4 3 7 1 5
1 4
1 3
1 4

Saída 1

Autor do problema: MIT, 2010