Bessie the cow and Farmer John have gone traveling to the city of Mootreepolis, but they were separated and now Bessie is lost. Farmer John has organized a search party to find her. For better or worse, the only way they have to locate her is by the direction of Bessie's moo (which is loud enough as to be heard anywhere in the city).
True to its name, Mootreepolis transportation is organized as a tree. In particular, the city has $N$ ($1 \le N \le 100,000$) locations conveniently numbered 0..$N$-1 and connected by $N$-1 bidirectional walkways such that there is a unique path between any pair of locations. Bessie is located at one of the $N$ locations in Mootreepolis.
The search party has fanned out so that one member of the search party is located at each of the $N$ locations. Farmer John can call any of them to get a report on the direction from which they heard Bessie's moo (i.e., which walkway leaving that location is in the direction of Bessie -- or perhaps that Bessie was actually found at that location).
However, Farmer John has an expensive mobile phone plan and wants to minimize the number of calls he makes. Your task is to tell Farmer John which locations to call in order to minimize the number of calls he has to make. In particular, Farmer John wants to ensure that he has to make no more than 20 calls before he can report Bessie's location.
NOTE: In 50% of inputs, $N$ will be at most 1000.
Your program should first read the Mootreepolis map description from standard input and then interact with the grader program via standard input and output (the console). The initial input will contain a description of Mootreepolis, such that each line contains a list of the walkways touching a given location. You should think of this list as having a zero-based index (relevant later for interaction with the grading program).
The first line of standard input contains $N$. The second and subsequent lines of standard input describe the neighbors of locations in Mootreepolis (starting with location 0). The first integer on each line is $K$ ($1 \le K \le N$), the number of neighbors of the location. This integer is followed by $K$ more integers $N_{0}$, $N_{1}$, ..., $N_{K-1}$ that are the zero-based indices of those neighbors. Two locations are neighbors if they are connected by a walkway.
Your program should print a sequence of locations to standard output. Each time you print a location to standard output, the grader program will respond with the index of the walkway in the direction of Bessie. The walkway will be given by its index on the relevant input line in the initial input. You should read this response from standard input.
If at any point you print the location at which Bessie is located, your program will be terminated. This will happen automatically, so you don't have to worry about doing it yourself. On QOJ, the grader closes the response stream when Bessie is found; terminate normally when reading a response reaches end of input.
The grader may choose its responses adaptively, but all its responses are consistent with at least one possible location of Bessie.
If you find Bessie, your program will be assigned a non-zero score: 10 if you used no more than 20 queries (including the current one), 0 if you used 30 queries or more. Otherwise, your score will be 30-(#queries made).
As a sample, suppose that Bessie is located at node 5 for the map below of Mootreepolis; the input descriptor is shown on the right:
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 4One possible interaction sequence is shown in the table below, where the query column indicates data sent to standard out, the response column indicates data read from standard in, and the location column contains the actual location that the response indicates. The details column shows the full ordered list of locations connected to the queried location along with the interpretation of the response (with <>'s):
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
From locations 2 and 6, location 3 is the closest neighbor to Bessie (and also the only neighbor). From location 3, location 4 is the closest neighbor to Bessie. From location 4, location 5 is the closest neighbor to Bessie. Bessie is in fact located at location 5, so the grading system terminates the program after it outputs 5.
Reactive Programs
In order to ensure that your program's output is not buffered inside your program; you must 'flush' your output.
For C and C++ users, if you're using stdio.h, include the line
setbuf(stdout, 0);
near the top of your program.
If you're using C++ iostream style I/O, flush each output line like this:
cout << line << "\n" << flush;
For Pascal, add the following statement after each writeln statement:
flush(stdout);
For Java, add the following after each output statement:
System.out.flush();
If your program 'times out' after you wrote a reply, it probably is not properly flushing the output.
JAVA USERS
Here is (we hope) the skeleton of input/output statements you will need:
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();
...Input
- Line 1: A single integer: $N$
- Lines $2..N+1$: Line $i+2$ contains multiple space-separated integers that describe the neighbors of location i in Mootreepolis: $K$, $N_{0}$, ..., $N_{K-1}$
Output
- Line none: write to standard out, not the output file.
Examples
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
Problem credits: MIT, 2010