Bessie và Farmer John thăm Mootreepolis nhưng tách nhau và cô bị lạc. Một đội tìm kiếm; chỉ hướng tiếng bò rống, nghe được khắp thành phố, giúp định vị.

Giao thông là cây như tên: $N$ nơi ($1 \le N \le 100,000$), số $0$..$N$-$1$, $N$-$1$ lối hai chiều, đường duy nhất giữa mỗi cặp. Bessie ở một trong $N$ nơi.

Mỗi nơi trong $N$ có một người tìm. FJ gọi để biết hướng tiếng rống, lối hướng tới cô, hoặc đã thấy cô ở đó.

Điện thoại đắt, muốn ít cuộc gọi nhất. Chọn nơi gọi, đặc biệt bảo đảm không quá $20$ trước khi báo vị trí.

Ghi chú: $50\%$ đầu vào có $N$ tối đa $1000$.

Đọc bản đồ từ đầu vào chuẩn, rồi tương tác với trình chấm qua vào/ra chuẩn. Mỗi dòng ban đầu liệt kê lối của một nơi, chỉ số danh sách từ không, cần cho tương tác sau.

Dòng đầu $N$, sau đó hàng xóm từ nơi $0$. Số đầu $K$ ($1 \le K \le N$) là số hàng xóm, rồi $K$ số nguyên $N_{0}$, $N_{1}$, …, $N_{K-1}$ là chỉ số hàng xóm từ không. Lối nối là hàng xóm.

In nơi liên tiếp ra đầu ra chuẩn. Mỗi trả lời là chỉ số lối hướng Bessie trong dòng đầu vào tương ứng. Đọc từ đầu vào chuẩn.

In nơi của cô tự động kết thúc. QOJ đóng luồng trả lời khi tìm thấy; kết thúc bình thường khi đọc trả lời tới hết đầu vào.

Trình chấm có thể thích nghi trả lời, nhưng mọi trả lời phù hợp ít nhất một vị trí có thể.

Tìm thấy thì thông báo điểm khác không: tối đa $20$ truy vấn kể cả hiện tại được $10$, $30$ trở lên được $0$, còn lại $30$ trừ số truy vấn.

Giả sử cô ở nút $5$ của bản đồ, mô tả đầu vào bên phải:

                               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

Bảng tương tác: query ra chuẩn, response vào chuẩn, location nơi trả lời chỉ. details danh sách hàng xóm đầy đủ có thứ tự và giải thích bằng <>:

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

Từ $2$, $6$, hàng xóm gần nhất và duy nhất $3$. Từ $3$ là $4$, từ $4$ là $5$. Cô ở $5$, in $5$ thì trình chấm kết thúc chương trình.

Chương trình tương tác

Đẩy đầu ra khỏi bộ đệm để không giữ dữ liệu trong chương trình.

C/C++ dùng stdio.h, thêm:

setbuf(stdout, 0);

gần đầu chương trình.

C++ iostream, đẩy mỗi dòng như sau:

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

Pascal sau mỗi writeln, thêm:

flush(stdout);

Java sau mỗi câu lệnh in, thêm:

System.out.flush();

Quá thời gian sau trả lời có thể do chưa đẩy đầu ra đúng.

Người dùng Java

Đây (hy vọng) là khung vào/ra cần thiết:

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út

Count: số lượng

Neighbors: hàng xóm

Query: truy vấn

Response: trả lời

Location: nơi

Neighbor list details: chi tiết danh sách hàng xóm

Done; program will be terminated: xong, chương trình kết thúc

write ...: ghi

read a reply: đọc trả lời

Dữ liệu vào

• Dòng $1$: số nguyên $N$.

• Các dòng $2..N+1$: dòng $i+2$ mô tả hàng xóm nơi $i$ bằng số nguyên cách nhau $K$, $N_{0}$, …, $N_{K-1}$.

Dữ liệu ra

• Không dòng trong tệp đầu ra: ghi ra đầu ra chuẩn, không ra tệp.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

Tác giả bài toán: MIT, 2010