Bessie e Farmer John visitano Mootreepolis, si separano e lei si perde. Un gruppo la cerca; solo la direzione del muggito, udibile in tutta la città, permette di localizzarla.

Il trasporto è un albero, come il nome: $N$ luoghi ($1 \le N \le 100,000$), numerati $0$..$N$-$1$, $N$-$1$ passaggi bidirezionali, unico cammino fra ogni coppia. Bessie in uno dei $N$ luoghi.

Un cercatore in ciascuno dei $N$ luoghi. FJ può chiamare per sapere direzione del muggito, quale passaggio porta verso lei, o che è lì.

Telefono caro, vuole minimo di chiamate. Scegli dove chiamare, garantendo in particolare al massimo $20$ per riferire la posizione.

Nota: nel $50\%$ degli input $N$ è al massimo $1000$.

Leggi prima la mappa dallo standard input, poi interagisci con valutatore tramite standard input/output. Ogni riga iniziale lista passaggi di un luogo; lista con indici da zero, utile dopo.

Prima riga $N$, seguenti: vicini dal luogo $0$. Primo $K$ ($1 \le K \le N$), numero dei vicini, poi $K$ interi $N_{0}$, $N_{1}$, …, $N_{K-1}$, loro indici da zero. Un passaggio definisce vicinanza.

Stampa luoghi in sequenza. Ogni risposta è indice del passaggio verso Bessie nella riga iniziale corrispondente. Leggi dallo standard input.

Stampare il suo luogo termina automaticamente. Su QOJ il valutatore chiude risposte al ritrovamento; termina normalmente a fine input leggendo una risposta.

Risposte possono essere adattive, ma tutte compatibili con almeno una posizione possibile.

Al ritrovamento si annuncia punteggio non nullo: fino a $20$ richieste inclusa attuale dà $10$, $30$ o più dà $0$, altre $30$ meno richieste fatte.

Sia Bessie nel nodo $5$ della mappa, descrizione input a destra:

                               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

Tabella interazione: query standard output, response standard input, location luogo indicato. details lista completa ordinata dei vicini e interpretazione in <>:

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

Da $2$, $6$, vicino più prossimo e unico $3$. Da $3$, $4$; da $4$, $5$. È in $5$, stampare $5$ termina il programma.

Programmi interattivi

Svuota l'output per non lasciarlo nel buffer.

C/C++ con stdio.h, includi:

setbuf(stdout, 0);

vicino all'inizio del programma.

C++ iostream, svuota ogni riga così:

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

Pascal dopo ogni writeln aggiungi:

flush(stdout);

Java dopo ogni output aggiungi:

System.out.flush();

Timeout dopo una risposta probabilmente indica output non svuotato correttamente.

Utenti Java

Ecco (speriamo) lo scheletro input/output necessario:

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: nodo

Count: conteggio

Neighbors: vicini

Query: richiesta

Response: risposta

Location: luogo

Neighbor list details: dettagli lista vicini

Done; program will be terminated: finito, programma terminerà

write ...: scrivere

read a reply: leggere risposta

Input

• Riga $1$: intero $N$.

• Righe $2..N+1$: riga $i+2$ descrive vicini del luogo $i$ con interi separati $K$, $N_{0}$, …, $N_{K-1}$.

Output

• Nessuna riga di file output: scrivi su standard output, non nel file.

Esempi

Input 1

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

Output 1

Autore del problema: MIT, 2010