Bessie i Farmer John odwiedzają Mootreepolis, rozdzielają się i ona ginie. Grupa jej szuka; jedyny sposób to kierunek muczenia, słyszalnego w całym mieście.

Transport jest drzewem, jak nazwa: $N$ miejsc ($1 \le N \le 100,000$), numery $0$..$N$-$1$, $N$-$1$ dwukierunkowych ścieżek, jeden szlak między każdą parą. Bessie w jednym z $N$ miejsc.

W każdym z $N$ miejsc jest poszukiwacz. FJ może zadzwonić o kierunek muczenia, którą ścieżką do niej, lub czy znaleziono ją tam.

Telefon drogi, chce minimum rozmów. Wskaż miejsca do dzwonienia, zwłaszcza gwarantując najwyżej $20$ przed podaniem pozycji.

Uwaga: w $50\%$ wejść $N$ najwyżej $1000$.

Najpierw czytaj mapę ze standardowego wejścia, potem rozmawiaj z oceniającym przez standardowe wejście/wyjście. Wstępne wiersze listują ścieżki miejsc; indeks listy od zera, potrzebny później.

Pierwszy wiersz $N$, następne sąsiedzi miejsc od $0$. Pierwsze $K$ ($1 \le K \le N$), liczba sąsiadów, następnie $K$ całkowitych $N_{0}$, $N_{1}$, …, $N_{K-1}$, indeksy sąsiadów od zera. Ścieżka oznacza sąsiedztwo.

Wypisuj kolejno miejsca. Odpowiedź to indeks ścieżki do Bessie w odpowiednim początkowym wierszu. Czytaj ją z wejścia.

Wypisanie jej miejsca kończy automatycznie. Na QOJ oceniający zamyka strumień odpowiedzi po znalezieniu; zakończ normalnie przy końcu wejścia podczas czytania.

Odpowiedzi mogą być adaptacyjne, ale wszystkie zgodne z co najmniej jedną możliwą pozycją.

Przy znalezieniu zapowiedziana ocena niezerowa: do $20$ pytań z bieżącym daje $10$, od $30$ daje $0$, pozostałe $30$ minus liczba pytań.

Niech Bessie będzie w węźle $5$ mapy, opis wejścia z prawej:

                               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 interakcji: query wyjście, response wejście, location wskazane miejsce. details pełna uporządkowana lista sąsiadów z interpretacją w <>:

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

Z $2$, $6$ najbliższy i jedyny sąsiad $3$. Z $3$ to $4$, z $4$ to $5$. Jest w $5$, wypisanie $5$ kończy program.

Programy interaktywne

Opróżniaj wyjście, by nie zostało w buforze.

C/C++ z stdio.h dodaj:

setbuf(stdout, 0);

blisko początku programu.

C++ iostream, opróżniaj każdą linię tak:

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

Pascal po każdym writeln dodaj:

flush(stdout);

Java po każdym wyjściu dodaj:

System.out.flush();

Limit czasu po odpowiedzi prawdopodobnie oznacza brak poprawnego opróżniania.

Użytkownicy Java

Oto (mamy nadzieję) szkielet potrzebnego wejścia/wyjścia:

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: węzeł

Count: liczba

Neighbors: sąsiedzi

Query: pytanie

Response: odpowiedź

Location: miejsce

Neighbor list details: szczegóły listy sąsiadów

Done; program will be terminated: gotowe, program zakończy się

write ...: pisz

read a reply: czytaj odpowiedź

Wejście

• Wiersz $1$: całkowite $N$.

• Wiersze $2..N+1$: wiersz $i+2$ opisuje sąsiadów miejsca $i$ całkowitymi oddzielonymi spacją $K$, $N_{0}$, …, $N_{K-1}$.

Wyjście

• Bez wiersza w pliku wyjścia: pisz na standardowe wyjście, nie plik.

Przykład

Wejście 1

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

Wyjście 1

Autor zadania: MIT, 2010