Bessie ו־Farmer John טיילו ב־Mootreepolis, נפרדו והיא אבדה. צוות מחפש; הרמז היחיד הוא כיוון הגעייה הנשמעת בכל העיר.

התחבורה עץ כשם העיר: $N$ מקומות ($1 \le N \le 100,000$), מספרים $0$..$N$-$1$, $N$-$1$ שבילים דו־כיווניים, מסלול יחיד בין כל זוג. היא באחד מ־$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