سافرت Bessie وFarmer John إلى Mootreepolis لكنهما افترقا وضلت. شكل فريق بحث؛ الطريقة الوحيدة اتجاه خوارها المسموع في كل المدينة.

النقل شجرة كما اسمها: $N$ مواقع ($1 \le N \le 100,000$)، مرقمة $0$..$N$-$1$، تربطها $N$-$1$ ممرات ثنائية الاتجاه، مسار وحيد بين أي موقعين. Bessie في أحد $N$ مواقع.

باحث في كل موقع من $N$. يمكن FJ الاتصال لمعرفة اتجاه الخوار، أي الممر نحوها، أو أنها في الموقع نفسه.

الهاتف غال، يريد أقل اتصالات. حدد المواقع للاتصال، خصوصًا ضمان لا أكثر من $20$ قبل الإبلاغ عن موقعها.

ملاحظة: في $50\%$ من المدخلات $N$ لا يتجاوز $1000$.

اقرأ الخريطة أولًا من الإدخال القياسي ثم تفاعل مع برنامج التقييم عبر الإدخال والإخراج القياسيين. كل سطر أولي قائمة ممرات موقع، فهرستها من صفر وتهم لاحقًا.

أول سطر $N$، التالية جيران المواقع بدءًا من $0$. أول صحيح $K$ ($1 \le K \le N$) عدد الجيران، يتبعه $K$ أعداد $N_{0}$ و$N_{1}$ و… و$N_{K-1}$، فهارس الجيران من صفر. الممر يعني الجوار.

اطبع المواقع تباعًا. كل رد فهرس الممر نحو Bessie في السطر الأصلي الموافق، واقرأه من الإدخال القياسي.

طباعة موقعها تنهي البرنامج آليًا. في QOJ يغلق المقيم تدفق الردود عند إيجادها؛ أنهِ طبيعيًا حين تصل قراءة الرد لنهاية الإدخال.

قد يختار المقيم الردود تكيفيًا لكن جميعها تتوافق مع موقع ممكن واحد على الأقل.

عند إيجادها يعلن نتيجة غير صفرية: حتى $20$ استعلامًا شاملة الحالي تعطي $10$، و$30$ فأكثر تعطي $0$، غير ذلك $30$ ناقص عدد الاستعلامات.

افترضها في العقدة $5$ بالخريطة، وصف الإدخال يمينًا:

                               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

جدول تفاعل: query للإخراج القياسي، response من الإدخال، location الموقع المشار إليه. details قائمة الجيران الكاملة المرتبة وتفسير الرد بـ<>:

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

من $2$ و$6$ أقرب جار والوحيد $3$. من $3$ هو $4$، ومن $4$ هو $5$. هي في $5$، طباعة $5$ تنهي البرنامج.

برامج تفاعلية

أفرغ الإخراج لئلا يبقى بمخزن البرنامج.

C/C++ مع stdio.h أضف:

setbuf(stdout, 0);

قرب بداية البرنامج.

C++ iostream، أفرغ كل سطر هكذا:

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

Pascal بعد كل writeln أضف:

flush(stdout);

Java بعد كل إخراج أضف:

System.out.flush();

تجاوز الزمن بعد الرد غالبًا يعني إفراغًا غير صحيح.

مستخدمو Java

هذا (نأمل) هيكل الإدخال والإخراج المطلوب:

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: عقدة

Count: عدد

Neighbors: جيران

Query: استعلام

Response: رد

Location: موقع

Neighbor list details: تفاصيل قائمة الجيران

Done; program will be terminated: تم، سينتهي البرنامج

write ...: كتابة

read a reply: قراءة رد

الإدخال

• السطر $1$: الصحيح $N$.

• الأسطر $2..N+1$: السطر $i+2$ يصف جيران الموقع $i$ بأعداد مفصولة $K$ و$N_{0}$ و… و$N_{K-1}$.

الإخراج

• لا سطر بملف إخراج: اكتب للإخراج القياسي وليس الملف.

أمثلة

الإدخال 1

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

الإخراج 1

مؤلف المسألة: MIT، 2010