Hercules

Time limit5sMemory limit1024 MB

Summary

Ostap must reach a hidden person in a tree of rooms by choosing corridors, learning only whether each move brought him closer or farther.

Level: Medium7 of 10
Topics: Tree, Graph, Simulation
Solved: No attempts yet

Problem

This is an interactive problem.

Ostap is chasing Skumbrievich, a half-responsible, half-ghostly comrade, through the corridors of Hercules. The building consists of several rooms connected by two-way corridors, so that any room can be reached from any other room by exactly one path (passing through other rooms along the way is allowed). Skumbrievich is in one of these rooms, and he does not move.

Each time he enters a new room, he cannot remember which corridor he came in through. He does see that the corridors connecting this room to its neighbors are numbered from 1 up to the number of corridors in that room. Ostap knows that the corridor numbering in each room never changes. The chase proceeds as follows.

Ostap chooses the number of the corridor he will take to another room.
He moves into the other room through that corridor.
In the new room, he again knows only the number of corridors in that room.
His inner voice tells him whether he got closer to Skumbrievich or farther away.
Possibly, he finally meets Skumbrievich, and then the chase ends.

Help Ostap catch the elusive Skumbrievich.

Hint

For the program to work correctly, you must flush the output after every output operation:

In Pascal: flush(output);
In C/C++: fflush(stdout);
In Java: System.out.flush();
In Python: sys.stdout.flush();

Also, end every printed line with a newline character.

Examples1

Example 1
Input
```
2
Colder
1
Warmer
2
Success
```
Expected output
```
1
1
2
```