Description

According to a newly unearthed batch of historical records, beneath a sand dune in the Taklamakan Desert lies a mysterious underground maze. An expedition team led by the famous explorer Aqiang kept digging and finally found the entrance to the underground maze. The team members were very excited and quickly climbed down to search for the long-buried secret.

As soon as they entered the maze, they heard a loud “boom”. Turning back, they found the entrance had merged into a stone wall and could no longer be identified. They realized they were trapped in the maze. Looking around, it seemed to be a cave.

This maze consists of many caves, and some pairs of caves are connected by passages. Each cave has a lamp. With the faint light, you can see how many passages are connected to this cave. The inside of every cave is exactly the same and cannot be marked. Every passage is also exactly the same and cannot be marked.

With the faint light, Aqiang noticed a line of text on the wall (in fact, every cave has this text). Translated into modern Chinese, it says: “Stranger, tell me the number of caves and the number of passages in this maze, and I will guide you out.”

Aqiang quickly calmed down. He took out a “signpost” and told the team: “This maze is far more dangerous than we imagined. For safety, everyone must move together. I have a signpost. With it, we can surely figure out the structure of the maze. Follow me!”

Now you will play the role of Aqiang. There is only one signpost. You can carry it with you, or temporarily leave it in some cave (leaving it on a passage is meaningless, because it is pitch-dark there and you cannot see anything). Your task is simple: use as few steps as possible to determine how many caves and how many passages the maze has. One “step” means walking from one cave to an adjacent cave.

Interaction Method

This is an interactive problem. Your program must interact with the judge library and must not access any file (including temporary files). The library provides several functions, with the following usage and effects:

• init must be called first, and can only be called once, for initializing the library.
• look(d,sign) checks the current cave. The library returns, via integer variable $d$, the number of passages connected to this cave, and via boolean variable sign, whether there is a signpost in this cave. sign is true if there is a signpost, and false otherwise.
• put_sign places the signpost in the current cave. This function can only be called when you are carrying the signpost.
• take_sign takes the signpost away from the current cave. This function can only be called when the signpost is in the current cave.
• walk(i) walks along the passage numbered $i$ to the adjacent cave. The numbering here is relative to the current cave, and is temporary. Suppose a cave has $d$ connected passages; these passages are numbered $0$, $1$, $2$, $\ldots$, $d-1$ in counterclockwise order. For the first move, the passage numbered $0$ is determined by the library. In the subsequent process, Aqiang will number the passage by which he entered this cave as $0$.
• report(n,m) reports the result to the library. $n$ is the number of caves, and $m$ is the number of passages. After this function is called, the library will terminate your program automatically.

Note: unlike other interactive problems, you must implement your program directly inside the main() function.

In C/C++, boolean variables are replaced by integers: $0$ means false, and $1$ means true.

5
3 2 3 4
2 1 3
2 1 2
2 1 5
1 4

Hint

Sample Explanation

Initially, the expedition team is in cave $1$. Passage $0$ leads to cave $2$, passage $1$ leads to cave $3$, and passage $2$ leads to cave $4$.

One possible full-score calling plan is as follows:

Calls by the C/C++ contestant	Explanation
init();	Initialize the program.
look(d, sign);	Returns $d=3$, $sign=false$.
put_sign();	Put down the signpost.
walk(0);	Choose the passage numbered $0$.
look(d, sign);	Returns $d=2$, $sign=false$.
walk(1);	Choose the passage numbered $1$.
look(d, sign);	Returns $d=2$, $sign=false$.
walk(1);	Choose the passage numbered $1$.
look(d, sign);	Returns $d=3$, $sign=true$.
take_sign();	Pick up the signpost.
walk(1);	Choose the passage numbered $1$.
look(d, sign);	Returns $d=2$, $sign=false$.
walk(1);	Choose the passage numbered $1$.
look(d, sign);	Returns $d=1$, $sign=false$.
report(5, 5);	Report that the number of caves is $5$ and the number of passages is $5$.

Note that this example only demonstrates how to use the library functions and has no algorithmic meaning.

Conventions

• The number of caves does not exceed $100$, and the number of passages does not exceed $4000$.
• The maze is connected, i.e. any two caves are reachable from each other.
• Between any two caves, there is at most one passage.
• No passage connects a cave to itself.

Scoring

If your program has any of the following issues, the score of this test point is $0$:

• It accessed any file (including temporary files) or terminated by itself.
• It made illegal calls to the library functions.
• It caused the library to exit abnormally.

Otherwise, your score for each test point is computed as follows:

If both the reported number of caves and the number of passages are incorrect, you get $0$ points. If exactly one of them is correct, you get $2$ points. If both are correct, then the score depends on the number of times walk is called, using the formula:

$$your\_score=\left\{ \begin{aligned} &10&,your\_ans\le our\_ans\\ &5+\left\lfloor\frac{our\_ans}{your\_ans}\times 5+0.5\right\rfloor&,your\_ans>our\_ans \end{aligned} \right.$$

Here, $your\_ans$ is the number of times your program calls walk, and $our\_ans$ is the result of our program.

How to Test Locally

• Create a file named dune.in in the working directory. The first line contains an integer $n$, the number of caves. The caves are numbered from 1 to n. The following $n$ lines describe the structure of the maze. Line $i+1$ describes cave $i$: the first number $d_i$ is the number of passages connected to this cave, and the following $d_i$ numbers list (in counterclockwise order) the cave numbers at the other ends of these passages.
• After calling init, the library uses cave $1$ as the starting cave of the expedition team, and temporarily sets that the passage numbered $0$ leads to the cave given by the second number on the second line of the file. For example, in the sample, initially the library temporarily sets that the passage numbered $0$ leads to cave $4$.
• Put your source file (named dune.cpp) and dune_lib.hpp in the same directory, and compile your program with the command g++ -o dune dune_lib.cpp dune.cpp.
• Run your program. The library will generate an output file dune.log, which contains the interaction record between your program and the library, as well as the final result.
• If the program ends normally, the last line of dune.log contains an integer, which is the number of steps you took.
• If the program exits illegally, we do not guarantee that the content of dune.log is meaningful.

Please download the sample interactive library from the problem attachments.

Translated by ChatGPT 5