32590번 - Galactic Expedition 다국어인터랙티브

The inhabitants of Flatland have finally managed to invent spacecraft, and send a hexagon to embark on a brave journey to explore their two-dimensional outer space. Their goal is to reach an ancient relic that might teach them about the absurd idea of a "third dimension". You are head of operations at the home base, coordinating the movements of the spaceship.

The spaceship has enough fuel to travel a certain distance in space, but it can be refuelled at the home base if necessary. Chances are high that the spaceship does not have enough fuel to travel to the relic directly, but you quickly discover that outer space is scattered with wormholes that allow the spaceship to teleport from one location to another. Your team manages to draw out a map with all the warp-points they can observe, but it is impossible to figure out which pairs of warp-points are connected to each other, except by flying through them. Time to start exploring!

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

The interactor first sends:

• One line with two integers $n$ and $d$ ($2\leq n\leq 500$, $n$ is even, $2\leq d\leq 10^6$), the number of points in outer space and the distance that your spaceship can travel with a full fuel tank.
• $n$ lines, the $i$th of which contains two integers $x$ and $y$ ($|x|, |y| \leq 10^6$), the coordinates of the $i$th point in outer space. Point $1$ corresponds to the home base, the relic is located at point $n$, and all other points are warp-points.

Then, your program should start travelling between these points, starting from point $1$. By printing a line containing an integer $i$ ($1 \leq i \leq n$), your spaceship will travel to the $i$th point.

When you travel to a warp-point, you will teleport through it and the interactor will respond with an integer $j$ ($1 < j < n$, $i \neq j$), indicating the warp-point that you have teleported to. This teleportation does not consume any fuel. Travelling to warp-point $j$ later will teleport you back to warp-point $i$. Teleportation only occurs when you explicitly travel to a warp-point, not when you happen to fly over other warp-points.

When you travel to point $1$, your fuel tank will be refilled when you reach it, and the interactor will always respond with $1$.

When you travel to point $n$, the interaction will stop.

It is guaranteed the shortest travel distance from point $1$ to any other point is at most $\frac{d}{2}$ when using the wormholes optimally.

The interactor is not adaptive: the wormhole links are fixed up front, and do not depend on how you decide to travel.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Running out of fuel or travelling to point $1$ more than $\frac{n}{2}$ times will result in a wrong answer.

• 1.in testing_tool.py